Tagged
• Data Structure
•

# 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.

# 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

1. java
2. cpp
3. 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:

• 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.

• 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 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.

• 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
`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

• 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

• 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 `

# Code Implementation

1. Java
2. Java With Generics
3. C++
4. 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 size39        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 Method136    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

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".

• 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

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.