JUSTIN LEONG

LinkedLists

A LinkedList is a data structure that represents a list of items that are connected in a linear sequence. The items in the list are represented by nodes that contain data such as strings, integers, characters, or objects. The data can be accessed by traversing each node in the sequence, starting at the head position, until reaching the desired node location. The LinkedList data structure can be created as either a singly or doubly LinkedList. The difference between a singly LinkedList and a doubly LinkedList is whether a node has access to only the next node in the list or if a node has access to both the previous and next nodes. A LinkedList with access to only the next node in the list is referred to as a singly LinkedList, while a LinkedList with nodes having access to their previous node in addition to the next node makes the list a doubly LinkedList.

Singly LinkedList

Doubly LinkedList

Code Implementation

In the following code implemention, I will be exaplaining how to create a singly LinkedList from scratch. In the singly LinkedList example, we have four node objects that each contain variables to store their integer value as well as a reference to the next node object in the list. The last node in the list is a special case since there is no object to point to, therefore its next reference will point to null. A LinkedList also requires a "head" which provides a reference to the first node object in order to gain access to the list.
To begin the implementation of a LinkedList we must first create a class that will act as a container which holds the nodes in the list. We will initialize this class as 'LinkedList' and configure the class to accept a generic object type to allow the user to specify the type of data being stored in the list. The generic typing is denoted by the angle brackets with the letter 'T' as a placeholder value. If you are unfamiliar with generic typing, just think of it as a way to allow users to select the type of data that the nodes should contain.

class

LinkedList<T>{

}
Once we have created our LinkedList class, we will need a way to create the nodes in our list. We can create these node objects by implementing a subclass called Node. The Node class will have a instance variable called 'data' which holds the contents of a node and a Node variable called 'next' that acts as a reference to the next node in the list. We will define a constructor inside of the Node class that will automatically assign the data variable to the value passed in by the user.

class

LinkedList<T>{

public class

Node{

T data;


Node next;



public

Node(T data){

this

.data = data;

}


}


}
To finish off the basic structure of the LinkedList, we will need a Node variable in the LinkedList class called 'head' which will point to the first node in the list. Without the head variable we will have no way of accessing the nodes in the list and thus this variable is very important as it is used in many of the LinkedList methods that we will be implementing next.

class

LinkedList<T>{

public class

Node{

T data;


Node next;



public

Node(T data){

this

.data = data;

}


}



Node head;


}
We have completed the basic structure of a LinkedList, however this class is not very useful since we are lacking a few of the fundamental methods that allow us to add and remove items from the list.
We will be implementing four methods that are critical to the functionality of the LinkedList. These four functions are described below:

isEmpty():

Returns whether a list is empty or not

add(T data):

Adds a new item to the end of the LinkedList

remove():

Removes and returns the oldest item added to the LinkedList

contains(T data):

Returns whether the lookup data exists in the list


isEmpty() Method

The isEmpty() method is a very straight forward method. If our list is empty then that means the head node is not assigned to a value. The method will check to see what the head node is assigned to and return whether the list is empty or not.

public boolean

isEmpty(){

if

(head ==

null

){

return true

;

}



return false

;
}


add() Method

The add() method allows us to create nodes and connect these nodes to our existing list. The logic behind this method is to traverse the existing list until reaching the last node in the list. We can then append this new node to the end of the list. To determine the last item in the list, we know that the last node will always have a 'next' value of null. Thus starting from the head of the list, we continue to traverse to the next node in the list as long as there is a valid node to traverse to. An edge case to consider is if the list is completely empty (head == null) and we are adding the first item to the list. Since an empty list basically means that we are at the end of the list, we can assign the head pointer to the new node.

public void

add(T data){

Node newNode =

 new

Node(data);

if

(head ==

null

){

head = newNode;


return

;

}



Node currentNode = head;


while

(currentNode.next !=

null

){

currentNode = currentNode.next;


}



currentNode.next = newNode;


}


remove() Method

The remove() method deletes the oldest item in the list which also happens to be whichever node the head node is pointed to. To remove a node from the list all we have to do is move the head position to point to the next node in the sequence. Prior to deleting the node, we want to store this in a variable so that we can return it at the end of the method. If the list is completely empty and a user attempts to remove an item, the method will automatically return null and exit.

public

Node remove(){

if

(head ==

null

){

return null

;

}



Node removedHead = head;


head = head.next;



return

removedHead;
}


contains() Method

The contains() method is very similar to the add() method as we are traversing through each of the nodes in the list, however before moving onto the next node we compare whether the current node's data matches with the lookup parameter. If we traverse through the entire list and are unable to find the data we are looking for then we return false.

public boolean

contains(T data){

if

(head ==

null

){

return false

;

}



Node currentNode = head;


while

(currentNode !=

null

){

if

(currentNode.data == data){

return true

;

}


currentNode = currentNode.next;


}



return false

;
}

Advantages and Disadvantages

Advantages Disadvantages
• When prepending an item to the list, this operation can be performed in constant time O(1) which is extremely quick and efficient

• When removing an item from the start of the list, this operation can be performed in constant time O(1) which is extremely quick and efficient

• LinkedLists are mutable which means that they are not restricted by size and items can continuously be added to the list
• Searching for an item in the list requires walking through each of the nodes starting from the head until reaching the desired node. This causes the lookup time to be of linear time complexity O(n), the worst-case scenario being where the lookup item is at the absolute end of the list

• Appending an item to the list takes linear time O(n) since one must walk through each of the nodes in the list until reaching the end of the list where one can then add the new item

• Removing an item from the end of the list requires traversing each of the nodes resulting in a linear time complexity. However, LinkedLists are generally used with the concept that the first item in would be the first item out (FIFO) which is what makes LinkedLists powerful.