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.
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.
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
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
;
}
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;
}
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;
}
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
;
}