# 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;45 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 head2Step 2 : If current is not null3Step 3 : Print current node data4Step 4 : Update current = current.next5Step 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 head2Step 2 : If current is not null3Step 3 : Compare current node value with given value4Step 4 : If current node value matches with given value, return true5Step 5 : else update current = current.next6Step 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 list3Step 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_NODE3Step 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 n23Step 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 next6Step 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 error3Step 3: head = head.next4Step 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 empty2Step 2 : Throw Error3Step 3 : Initialize current to head and prev to null4Step 4 : Repeat Step 5 to until current.next != null5Step 5 : Update prev to current and current to current.next6Step 6 : update prev.next to null (As current node is last node and7 prev node next should be updated to null to delete last node)8Step 7 : update tail to prev9Step 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 empty2Step 2 : Throw Error3Step 3 : Initialize current to head and prev to null4Step 4 : Repeat Step 5 to until current.next != null5Step 5 : Update prev to current and current to current.next6Step 6 : update prev.next to null (As current node is last node and7 prev node next should be updated to null to delete last node)8Step 7 : update tail to prev9Step 8 : Exit

## Video Explanation

# Code Implementation

- Java
- Java With Generics
- C++
- Python

1public class LinkedList {23 class Node {4 int val;5 Node next;67 Node(int val){8 this.val = val;9 }10 }1112 private Node head;13 private Node tail;1415 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 }2526 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 }3637 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 }5354 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 }6667 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;7980 while (current.next != null){81 prev = current;82 current = current.next;83 }84 prev.next = null;85 tail = prev;86 return current.val;87 }8889 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;99100 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 }109110 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 }120121 public boolean isEmpty(){122 return head == null ;123 }124125126 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 }134135 // Driver Method136 public static void main(String[] args) {137 LinkedList ll = new LinkedList();138139 ll.addFirst(20);140 System.out.print("After Adding 20 at First : ");141 ll.print();142143 ll.addFirst(10);144 System.out.print("After Adding 10 at First : ");145 ll.print();146147 ll.addLast(30);148 System.out.print("After Adding 30 at Last : ");149 ll.print();150151 ll.addLast(40);152 System.out.print("After Adding 40 at Last : ");153 ll.print();154155 ll.addFirst(5);156 System.out.print("After Adding 5 at First : ");157 ll.print();158159 ll.add(4, 25);160 System.out.print("After Adding 25 at Pos 4 : ");161 ll.print();162163 ll.deleteFirst();164 System.out.print("After Deleting First Node: ");165 ll.print();166167 ll.deleteLast();168 System.out.print("After Deleting Last Node : ");169 ll.print();170171 ll.delete(3);172 System.out.print("After Deleting at Pos 3 : ");173 ll.print();174175 }176177178}

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