Tagged

Linked List Data Structure & its Characteristics

Introduction

Linked List is a linear collection of data elements/objects. The elements of the linked list are known as a node and the objects of the linked list are randomly stored in memory.

Characteristics

Linked list is a linear data structure. Linked list nodes are stored randomly in memory and are allocated during run time. Each node consists of value/data and a pointer/link which is the address of the next node in the linked list. Linked list uses extra memory to store links. Linked List can grow or shrink at any point of time easily. No need to know the size of the elements during initialization of the linked list. First node of the linked list is called as Head Last node next always points to null.

List Node Representation

Each node in a linked list consists of two parts:

Value of the node
Pointer to the next node

Value of the node can be any data type like int, float, double, String or any user defined data type as well.

The first node of the linked list is referred to as head and the last node of the linked list is referred as tail.

Below is the node representation in programmatically for int data type

java
cpp
python

1public class ListNode {
2    int value;
3    ListNode next;
4
5    public ListNode(int val) {
6        this.value = val;
7    }
8}

Operations

For linked list operations we use two pointers which are head and tail. Head always points to first element of the linked list and tail always points to last element present in the linked list.

Linked list is a linear data structure and allows following basic operation:

Insertion : adds a new element to the linked list
Deletion : delete existing element form the linked list
Searching : search for an element by its value in the linked list
Traversal : traverse all elements starting form head in the linked list

Traversal

Accessing the nodes of the linked list in order is called traversal. Traversal operation is needed to perform the tasks like

Printing the content of the linked list.
Searching for an element in the linked list.
Inserting new node at a given position.
Deleting the node at a given position.

Linked list is always represented using its head node and at any node we always have access to know what is next node of the current node. So to traverse the linked list we always start with head node of the linked list. To understand how traversal of linked list works, lets assume that we need to print contents of the linked list. Below is the algorithm to traverse the list and print the data.

Initialize current to head node of the linked list
If the current node is not null, print the data of the current node.
Now move to the next node updating current to address of the next node.
Continue the same process until we reach the end of the linked list.( i.e., until current node is null)

1Step 1 : Initialize current to head 
2Step 2 : If current is not null  
3Step 3 : Print current node data  
4Step 4 : Update current = current.next 
5Step 5 : Repeat Steps 2 to 5 until current is not null

Search

Search operation involves finding the given element present in the linked list or not. To do this, we need to traverse the list which is discussed in traversal algorithm and while traversing instead of displaying the data, we need to check whether the current node values matches with the given value or not.

Initialize current to head node of the linked list
If current node is not null, compare node value with given value
If the node value matches with given value, return true
else we need to move to next node by updating current node to its next node.
We continue the process until we reach end of the linked list

1Step 1 : Initialize current to head 
2Step 2 : If current is not null 
3Step 3 : Compare current node value with given value 
4Step 4 : If current node value matches with given value, return true 
5Step 5 : else update current = current.next 
6Step 6 : Repeat steps 2 to 5 until current is not null

Insertion

Inserting or adding new node mainly happens at 3 places which are given below :

Inserting new node at the beginning
Inserting new node at the end
Inserting new node at random position of the linked list.

Inserting new node at the beginning

Create new node as NEW_NODE
Mark NEW_NODE next to head
Update head to NEW_NODE

1Step 1 : Create new node "NEW_NODE" for given data (or value) 
2Step 2 : Mark NEW_NODE next to head of the linked list 
3Step 3 : Update head pointer to NEW_NODE

Inserting new node at the end

In linked list we are maintaining two pointers, one is head and the other is tail. Head represents the linked list, tail is used whenever we need to add new node at the end. If we do not maintain tail node, insertion at end takes O(n) time complexity as first we need to traverse the list till last node and then we need to create. Maintaining tail node simplifies inserting the new node at the end of the list with just o(1) time complexity.

1Step 1: Create new node "NEW_NODE" for given data (or value) 
2Step 2: Mark tail node next to NEW_NODE  
3Step 3: Update tail pointer to NEW_NODE

Inserting new node at given position

Initialize current to head node of the linked list
Move current node pos-1 times (Traverse the list by pos-1 times)
Create new node and update new node next as current node next node
Now update current node next as newly created node.

1Input: position n 
2
3Step 0: Traverse the list until we reach the node (CURRENT_NODE) which is at n-1 position.  
4Step 1: Create new node "NEW_NODE" for given data (or value) 
5Step 3: Mark NEW_NODE next to CURRENT_NODE next  
6Step 3: Mark CURRENT_NODE next to NEW_NODE

Delete / Remove

To delete a node we always need to perform these below steps :

Find the previous (PREV_NODE) and next (NEXT_NODE) nodes of the node to be deleted.
Update PREV_NODE node next pointer to NEXT_NODE
Free the memory of the deleted node.

Removing node mainly happens at 3 places which are given below :

Deleting node at the beginning
Deleting node at the end
Deleting node at random position of the linked list.

Deleting node at the beginning

If we want to delete at the beginning, the head of the linked list changes to next node of the head. Below is the algorithm to delete the node at the beginning

1Step 1: If list is empty (head is null) 
2Step 2: Throw error  
3Step 3: head = head.next 
4Step 4: Exit

Deleting node at the end

Initialize current to head node of the linked list
Move current node until we reach the node which is previous to last node of the linked list
Now Mark current node next as null
Update last node to current node.

1Step 1 : If list is empty 
2Step 2 : Throw Error 
3Step 3 : Initialize current to head and prev to null 
4Step 4 : Repeat Step 5 to until current.next != null 
5Step 5 : Update  prev to current and current to current.next  
6Step 6 : update prev.next to null (As current node is last node and 
7          prev node next should be updated to null to delete last node) 
8Step 7 : update tail to prev 
9Step 8 : Exit

Deleting node at specific position

To delete a node CURRENT_NODE, we need two nodes, one is the node which is previous to CURRENT_NODE and the other is the node which is next to CURRENT_NODE.

Initialize current to head node and prev node as null
Move current node pos-1 times. i.e., prev will be updated to current and current will be updated to current node next.
Now mark prev node next to current node next (i.e the current node will be out from the linked list).

1Step 1 : If list is empty  
2Step 2 : Throw Error 
3Step 3 : Initialize current to head and prev to null 
4Step 4 : Repeat Step 5 to until current.next != null 
5Step 5 : Update  prev to current  and current to current.next 
6Step 6 : update prev.next to null (As current node is last node and 
7        prev node next should be updated to null to delete last node) 
8Step 7 : update tail to prev 
9Step 8 : Exit

Video Explanation

Code Implementation

Java
Java With Generics
C++
Python

1public class LinkedList {
2 
3    class Node {
4        int val;
5        Node next;
6 
7        Node(int val){
8            this.val = val;
9        }
10    }
11 
12    private Node head;
13    private Node tail;
14 
15    public void addFirst(int val){
16        if(isEmpty()) {
17            head = new Node(val);
18            tail = head;
19            return;
20        }
21        Node newNode = new Node(val);
22        newNode.next = head;
23        head = newNode;
24    }
25 
26    public void addLast(int val){
27        if(isEmpty()) {
28            head = new Node(val);
29            tail = head;
30            return;
31        }
32        Node newNode = new Node(val);
33        tail.next = newNode;
34        tail = newNode;
35    }
36 
37    public void add(int pos, int val){
38        // validate pos using size
39        if( pos == 1 ){
40            addFirst(val);
41            return;
42        }
43        Node current = head;
44        int count = 1;
45        while(count < pos-1) {
46            count++;
47            current = current.next;
48        }
49        Node newNode = new Node(val);
50        newNode.next = current.next;
51        current.next = newNode;
52    }
53 
54    public int deleteFirst(){
55        if(isEmpty()) {
56            throw new RuntimeException("List is Empty");
57        }
58        Node current = head;
59        head = head.next;
60        current.next = null;
61        if(isEmpty()) {
62            tail = null;
63        }
64        return current.val;
65    }
66 
67    public int deleteLast() {
68        if(isEmpty()) {
69            throw new RuntimeException("List is Empty");
70        }
71        if(head == tail) {
72            int val = head.val;
73            head = null;
74            tail = null;
75            return val;
76        }
77        Node current = head;
78        Node prev = null;
79 
80        while (current.next != null){
81            prev = current;
82            current = current.next;
83        }
84        prev.next = null;
85        tail = prev;
86        return current.val;
87    }
88 
89    public int delete(int pos){
90        if(isEmpty()) {
91            throw new RuntimeException("List is Empty");
92        }
93        if(pos == 1) {
94            deleteFirst();
95        }
96        Node current = head;
97        Node prev = null;
98        int count = 1;
99 
100        while(count < pos) {
101            count++;
102            prev = current;
103            current = current.next;
104        }
105        prev.next = current.next;
106        current.next = null;
107        return current.val;
108    }
109 
110    public boolean search(int val){
111        Node current = head;
112        while(current != null){
113            if(val == current.val) {
114                return true;
115            }
116            current = current.next;
117        }
118        return false;
119    }
120 
121    public boolean isEmpty(){
122        return head == null ;
123    }
124 
125 
126    public void print(){
127        Node current = head;
128        while(current != null){
129            System.out.print(current.val +" -> ");
130            current = current.next;
131        }
132        System.out.println("NULL");
133    }
134 
135    // Driver Method
136    public static void main(String[] args) {
137        LinkedList ll = new LinkedList();
138 
139        ll.addFirst(20);
140        System.out.print("After Adding 20 at First : ");
141        ll.print();
142 
143        ll.addFirst(10);
144        System.out.print("After Adding 10 at First : ");
145        ll.print();
146 
147        ll.addLast(30);
148        System.out.print("After Adding 30 at Last  : ");
149        ll.print();
150 
151        ll.addLast(40);
152        System.out.print("After Adding 40 at Last  : ");
153        ll.print();
154 
155        ll.addFirst(5);
156        System.out.print("After Adding  5 at First : ");
157        ll.print();
158 
159        ll.add(4, 25);
160        System.out.print("After Adding 25 at Pos 4 : ");
161        ll.print();
162 
163        ll.deleteFirst();
164        System.out.print("After Deleting First Node: ");
165        ll.print();
166 
167        ll.deleteLast();
168        System.out.print("After Deleting Last Node : ");
169        ll.print();
170 
171        ll.delete(3);
172        System.out.print("After Deleting at Pos 3  : ");
173        ll.print();
174 
175    }
176 
177 
178}

Code Video Explanation

Advantages and Disadvantages

To understand the advantages/disadvantages of linked lists more clearly, let us assume we need to store student names who are enrolled for a course named "Mathematics In Computing" in a linked list alphabetically and the max capacity of the students is fixed and is 15. At the moment only 5 students have been enrolled and the names of the students in alphabetic order are "Alex", "Bob", "Danie", and "Roxie".

Advantages

There is no need to specify size of the linked list during initialization, so it’s easy to grow or shrink a linked list without any extra operations.
Sometimes even if we want to limit the max capacity of a data to store in a data structure, we might not be using max capacity. These scenarios linked list is the best data structure when compared to arrays, as memory allocation is always dynamic in nature. For example if the max capacity of the linked list was declared as 15 and only 7 students enrolled for the course “Mathematics In Computing ”. Here memory is occupied for 7 students and whenever we add a new student we just check whether it reaches max capacity or not. We don’t block any memory for max capacity.
Insertion at start position of the linked list : If a new student named Adam enrolled for the course "Mathematics In Computing", to maintain alphabetic order of the students, the correct position of Adam should be at the start of the linked list. So we just do below operations :
- Adam next points to Alex
- Head of the linked list changes from Alex to Adam.

As we are adding the new node at the start, insertion of any new student at the start position always takes O(1).

Insertion at end position of the linked list : If a new student named "Theressa" enrolled for the course “Mathematics In Computing”, to maintain alphabetic order of the students, the correct position of Theressa should be at the end of the linked list. So we just do below operations:
- Roxie next points to Theressa
- Tail of the linked list changes from Roxie to Theressa As we are maintaining the tail of the linked list, insertion of any new student at the end position always takes O(1).

Delete Operation : If any student wants to withdraw from the course, we can perform this operation in constant time complexity. For example if Adam wants to withdraw from the course, and here Adam is the head (first/start node) of the linked list, we just perform below operations:
- Point head to head.next which is Alex So once we know the node placeholder, deletion of the student always takes O(1).

Linked list data structure used to create data structures like Queue, Stack etc.

Disadvantages

In the linked list, nodes in memory are stored at random and so a separate pointer or link is needed to connect successive elements. It means there is some extra space needed to store the pointer’s.
Random access of the elements in the linked list is not possible, to get any element information, it is always needed to start traversing from the head node of the linked list .
Reverse traversing is not possible, as in the linked list for any node we have only reference to the next node.

...