Most common definition of Linked lists is that they are linear or sequential data structures in which elements are stored at non-contiguous memory locations and are linked to one another using pointers.
A Linked List is a sequence of links that contains items. Each link contains a connection to another link. Linked lists are the second most used data structure after arrays.
Like arrays, linked lists are also linear data structures, but in linked lists, elements are not stored at contiguous memory locations. They can be stored anywhere in the memory, but for sequential access, the nodes are linked to each other using pointers.
Below are few terms that are useful for understanding more about LinkedList:
- Link: Each link of a linked list contains data of a node called an element.
- Next: Each link contains the address(link) of the next element called next.
Types of Linked List
Following the types of linked list:
- Single Linked List: Nodes can be navigated in forward direction.
- Doubly Linked List: Nodes can be navigated in forward as well as backward direction.
- Circular Linked List: Last node has the address(link) of First node as next and First node has the address(link) of the last node as prev.
Singly Linked List
Basic Operations
- Insertion: add an element to the list.
- Deletion: delete an element from the list.
- Display: display list.
- Search: search an element from the list.
Basic code of single linked list:
class LinkedList {
Node head;
static class Node {
int data;
Node next;
//constructor
Node(int newData) {
data = newData;
next = null;
}
}
public static void main(String[] args) {
LinkedList list = new LinkedList(); //empty Linked List
//inserting 3 nodes with data
list.head = Node(10);
Node secondNode = Node(20);
Node thirdNode = Node(30);
//providing address(link) to the nodes
list.head.next = secondNode; //Linked first node to the second node
secondNode.next = thirdNode; //Linked second node to the third node
}
}
Insertion Operation
As we already have a head node of a linked list, our goal is to insert new nodes in the already created linked lists.
There can be many conditions/situations you may run into while inserting a node. The frequent ones are listed below:
- Insert a node at the start of the list.
- Insert a node after any other node.
- Insert a node at the end of the list.
Insert a node at the start of the list
Inserting a node at the start of the list can be done by inserting the node before the head of the list, and then the newly added node will become the head of the given list.
The below function is in the above sample code of Linked List.
public void insertAtFirst(int data) {
//Allocate and insert data
Node atFirst = new Node(data);
//Point next of the newly added node to head
atFirst.next = head;
//Point head to the newly added node
head = atFirst;
}
Time Complexity of inserting the node at first is O(1).
Insert a node after another node
Inserting a node after another node is similar to inserting a node first. We have to create a new node and assign the pointer of the newly inserted node with the previous node and the next pointer of the previous node to the newly created node.
The below function is in the above sample code of Linked List.
public void insertAfterNode(Node previousNode, int data) {
//check if previous Node is null
if (previousNode == null) return;
//Allocate and insert data
Node newNode = new Node(data);
//Point next of the newly added node to head
newNode.next = previousNode.next;
//Point next to the newly added node
previousNode.next = newNode;
}
Time Complexity of inserting the node after another node is O(1).
Insert a node at the end of the list.
Inserting a node at the end of the list is done by always adding the new node at the last node of the list. For this, we must traverse the linked list to the end in order to get the pointer pointing to the last node.
The below function is in the above sample code of Linked List.
public void insertAtLast(int data) {
//Allocate and insert data
Node newNode = new Node(data);
//check if head is null then assign new node to head
if (head == null) {
head = newNode;
return;
}
//Assign next of new node to null(as last node)
newNode.next = null;
Node lastNode = head;
//traverse till the last node to get pointer of last node
while (lastNode.next != null) {
last = last.next;
}
//change next of the last node to the n
last.next = newNode;
return;
}
Time Complexity of inserting the node at the end is O(n).
Deletion Operation
As we already have the pointer of the head that is pointing to the head node of the linked list, along with the node value that will be deleted from the list.
Similar to inserting, there are different scenarios for deleting a node from a linked list. Some frequent ones are listed below:
- Delete the first occurrence of a given data value.
- Delete the node at the given position.
- Delete a node whose pointer is given.
Delete the first occurrence of a given data value
For this, we need to traverse the list until we found the node to be deleted. Check for the node just before the node that will be deleted. Once we have found the node before the node to be deleted, we need to update its next pointer to the next of its node.
The below function is in the above sample code of Linked List.
public void deleteFirstOccurenceNode(int data) {
//store head node in temp.
Node temp = head;
Node prev = null;
if (temp != null && temp.data == data) {
head = temp.next; //change head
return;
}
//search for the node to be deleted
while (temp != null && temp.data != data) {
prev = temp;
temp = temp.next;
}
//if data was not present in linked list
if (temp == null) {
return;
}
//unlink the node from the linked list
prev.next = temp.next;
}
Time Complexity of deleting the first occurrence of a given data value is O(n).
Delete the node at the given position
Deleting a node at a given position can be achieved depending on the node positions. Nodes can be present at:
For all of these, we have a different approach for all positions, we will write a generic function that will work for all positions, whether beginning, middle or last.
If we want to delete a node present at the beginning of the linked list, we can simply delete it by updating the head pointer to point to the next of the root node. Or, if want to delete a node present at middle, we must have the pointer to the node previous to the node to be deleted. If position is nonzero, run the loop for position one time, and then follow the same approach to delete the first node as discussed above.
public void deleteNodeAtPosition(int pos) {
//if list is empty
if (head == null) {
return;
}
Node temp = head;
//If given position is beginning
if (pos == 0) {
head = temp.next;
return;
}
//find previous node of the node to be deleted
for (int i = 0; temp != null && i < pos - 1; i++) {
temp = temp.next;
}
//if position is more then the nodes in list
if (temp == null || temp.next == null) {
return;
}
Node next = temp.next.next;
//unlink the deleted node from the list
temp.next = next;
}
Time Complexity of deleting the node at a given position is O(n).
Deleting a node whose pointer is given
In this case, a pointer is given that is pointing to a particular node in the linked list, and we have to delete the node. This can be done by finding a node just previous to it and updating its pointer.
The best solution is to copy the data from the next node to the node to be deleted, and delete the next node.
public void deleteNodeAtPointer(Node nodeToDelete) {
Node temp = nodeToDelete.next;
nodeToDelete.data = temp.data;
nodeToDelete.next = temp, next;
System.gc();
}
Time Complexity of deleting the node is O(n).
Note
This approach will work only if the given node does not point to the last node. This is because if it is the last node, you won't have the next node to copy the data.
Display Operation
This is simply iterating the list from the start to the end of the list. Below is the display method to iterate the list.
public void display() {
//Current node will point to head
Node current = head;
if (head == null) {
System.out.println("Empty List");
return;
}
while (current != null) {
System.out.println(current.data + " ");
current = current.next;
}
System.out.println();
}
Time Complexity of displaying the list is O(n).
Search Operation
Searching an element in a list can be achieved by traversing the linked list from the start node. Keep traversing until we find the element in the list.
Below is the implementation method of the Search operation.
public int searchNode(int data) {
if (head == null) {
System.out.println("Empty List");
return;
}
int index = 0;
Node temp = head;
//traverse through the list
while (temp != null) {
//Returns the index if found
if (temp.data == data) {
return index;
}
index++;
temp = temp.next;
}
//returns -1 if element not found
return -1;
}
Summary
Here, we come to the end of the article about Basic operations with Linked List. But before finishing, we will summarize what we learned.
What did we learn?
- What a linked list is
- Basic Operations, including Insertion, Deletion, Searching and Traversing Operation.
- Including Insertion and Deletion Operation with Border cases.