Introduction to Linked List - Data Structure and Algorithm Tutorials - GeeksforGeeks (2024)

Linked List is basically chains of nodes where each node contains information such as data and a pointer to the next node in the chain. It is a popular data structure with a wide range of real-world applications. In this article, we will provide a complete introduction of Linked List, which will help you tackle any problem based on Linked List.

What is a Linked List?

Linked List is a linear data structure which looks like a series of nodes, where each node has two parts: data and next pointer. Unlike Arrays, Linked List elements are not stored at a contiguous location.In the linked list there is a head pointer, which points to the first element of the linked list, and if the list is empty then it simply points to null or nothing.

Basic Terminologies of Linked List

• Head: The Head of a linked list is a pointer to the first node or reference of the first node of linked list. This pointer marks the beginning of the linked list.
• Node: Linked List consists of a series of nodes where each node has two parts: data and next pointer.
• Data: Data is the part of node which stores the information in the linked list.
• Next pointer: Next pointer is the part of the node which points to the next node of the linked list.

Importance of Linked List

Here are a few advantages of a linked list that is listed below, it will help you understand why it is necessary to know.

• Dynamic Data structure: The size of memory can be allocated or de-allocated at run time based on the operation insertion or deletion.
• Ease of Insertion/Deletion: The insertion and deletion of elements are simpler than arrays since no elements need to be shifted after insertion and deletion, Just the address needed to be updated.
• Efficient Memory Utilization: As we know Linked List is a dynamic data structure the size increases or decreases as per the requirement so this avoids the wastage of memory.
• Implementation: Various advanced data structures can be implemented using a linked list like a stack, queue, graph, hash maps, etc.

Types of Linked List

There are mainly three types of linked lists:

1. Singly linked list
2. Doubly linked list
3. Circular linked list

1. Singly Linked List

Singly Linked List is a type of linked list where each node has two parts: data and next pointer. The data part stores the information and the next pointer points to the next node of the linked list. The next pointer of the last node stores null as it is the last node of the linked list and there is no next node. Traversal of items can be done in the forward direction only due to the linking of every node to its next node.

Node Definition of Singly Linked List

// Singly linked list node in C++class Node {public:  // Data field int data;  // Pointer to the next node Node* next; // Constructor to initialize a new node with data Node(int new_data) { this->data = new_data; this->next = nullptr; }};

// Singly linked list node in Cstruct Node { // Data field int data; // Pointer to the next node struct Node* next;};

// Singly linked list node in Javaclass Node { // Data field int data; // Next node Node next; // Constructor to initialize a new node with data Node(int new_data) { data = new_data; next = null; }}

# Singly linked list node in Pythonclass Node: # Constructor to initialize a new node with data def __init__(self, new_data): # Data field self.data = new_data # Next node self.next = None

// Singly linked list node in C#public class Node { // Data field public int data; // Next node public Node next; // Constructor to initialize a new node with data public Node(int new_data) { data = new_data; next = null; }}

// Singly linked list node in Javascriptclass Node { // Constructor to initialize a new node with data constructor(new_data) { // Data field this.data = new_data; // Next node this.next = null; }}

Basic Operations on Singly Linked List

The following are some basic operations performed on a Single Linked List:

• Insertion: The insertion operation can be performed in three ways. They are as follows:
  • Inserting At the Beginning of the list
  • Inserting At End of the list
  • Inserting At Specific location in the list
• Deletion: The deletion operation can be performed in three ways. They are as follows:
  • Deleting from the Beginning of the list
  • Deleting from the End of the list
  • Deleting a Specific Node
• Traverse: This process displays the elements of a Single-linked list.
• Search: It is a process of determining and retrieving a specific node either from the front, the end or anywhere in the list.

2. Doubly Linked List:

Doubly Linked List is a type of linked list where each node has three parts: data, next pointer and previous pointer. The data part stores the information, the next pointer points to the next node of the linked list and the previous pointer points to the previous node of the linked list. The next pointer of the last node and the previous pointer of the first node stores null. Traversal of items can be done in the forward direction as well as backward direction due to the linking of every node to its next node as well as the previous node.

Node Definition of Doubly Linked List:

// Doubly linked list node in C++class Node {public: // Data field int data; // Pointer to previous node Node* prev; // Pointer to the next node Node* next; // Constructor to initialize a new node with data Node(int new_data) { this->data = new_data; this->next = nullptr; this->prev = nullptr; }};

// Doubly linked list node in Cstruct Node { // Data field int data; // Previous node Node* prev; // Next node Node* next;};

// Doubly linked list node in Javaclass Node { // Data field int data; // Previous node Node prev; // Next node Node next; // Constructor to initialize a new node with data Node(int new_data) { this.data = new_data; this.prev = null; this.next = null; }}

# Doubly linked list node in Pythonclass Node: # Constructor to initialize a new node with data def __init__(self, new_data): # Data field self.data = data # Previous node self.prev = None # Next node self.next = None

// Doubly linked list node in C#public class Node { // Data field public int data; // Previous node public Node prev; // Next node public Node next; // Constructor to initialize a new node with data Node(int new_data) { this.data = new_data; this.prev = null; this.next = null; }}

// Doubly linked list node in Javascriptclass Node { // Constructor to initialize a new node with data constructor(new_data) { // Data field this.data = new_data; // Previous node this.prev = null; // Next node this.next = null; }}

Operations on Doubly Linked List:

In a doubly linked list, we perform the following operations…

• Insertion: The insertion operation can be performed in three ways as follows:
  • Inserting At the Beginning of the list
  • Inserting after a given node.
  • Inserting at the end.
  • Inserting before a given node
• Deletion: The deletion operation can be performed in three ways as follows…
  • Deleting from the Beginning of the list
  • Deleting from the End of the list
  • Deleting a Specific Node
• Display: This process displays the elements of a double-linked list.

3. Circular Linked List:

A circular linked list is a type of linked list in which the first and the last nodes are also connected to each other to form a circle, there is no NULL at the end.

Commonly used operations on Circular Linked List:

The following operations are performed on a CircularLinked List

• Insertion: The insertion operation can be performed in three ways:
  • Insertion in an empty list
  • Insertion at the beginning of the list
  • Insertion at the end of the list
  • Insertion in between the nodes
• Deletion: The deletion operation can be performed in three ways:
  • Deleting from the Beginning of the list
  • Deleting from the End of the list
  • Deleting a Specific Node
• Display: This process displays the elements of a Circular linked list.

Implementation of Linked List:

Below is the implementation of Linked List in different languages:

// C++ program to show the implementation of singly linked// list#include <bits/stdc++.h>using namespace std;// A linked list nodeclass Node {public: int data; Node* next; // Constructor to initialize a new node with data Node(int new_data) { data = new_data; next = nullptr; }};// Function to print the linked listvoid printList(Node* head) { // Loop that runs till head is nullptr while (head != nullptr) { // Printing current node data cout << " " << head->data; // Moving to the next node in the list head = head->next; } cout << "\n";}// Driver codeint main() { // Create a hard-coded linked list: // 2 -> 3 -> 4 -> 5 -> 6 Node* head = new Node(2); head->next = new Node(3); head->next->next = new Node(4); head->next->next->next = new Node(5); head->next->next->next->next = new Node(6); // Printing the above list cout << "Linked List:"; printList(head); return 0;}

// C program to show the implementation of singly linked// list#include <stdio.h>#include <stdlib.h>// A linked list nodestruct Node { int data; struct Node* next;};// Constructor function to initialize a new node with datastruct Node* createNode(int new_data) { struct Node* new_node = (struct Node*)malloc(sizeof(struct Node)); new_node->data = new_data; new_node->next = NULL; return new_node;}// Function to print the linked listvoid printList(struct Node* head) { // Loop that runs till head is NULL while (head != NULL) { // Printing current node data printf(" %d", head->data); // Moving to the next node in the list head = head->next; } printf("\n");}// Driver codeint main() { // Create a hard-coded linked list: // 2 -> 3 -> 4 -> 5 -> 6 struct Node* head = createNode(2); head->next = createNode(3); head->next->next = createNode(4); head->next->next->next = createNode(5); head->next->next->next->next = createNode(6); // Printing the above list printf("Linked List:"); printList(head); return 0;}

// Java program to show the implementation of singly linked// list// A linked list nodeclass Node { int data; Node next; // Constructor to initialize a new node with data Node(int new_data) { data = new_data; next = null; }}public class GfG { // Function to print the linked list public static void printList(Node head) { // Loop that runs till head is null while (head != null) { // Printing current node data System.out.print(" " + head.data); // Moving to the next node in the list head = head.next; } System.out.println(); } // Driver code public static void main(String[] args) {  // Create a hard-coded linked list: // 2 -> 3 -> 4 -> 5 -> 6 Node head = new Node(2); head.next = new Node(3); head.next.next = new Node(4); head.next.next.next = new Node(5); head.next.next.next.next = new Node(6); // Printing the above list System.out.print("Linked List:"); printList(head); }}

# Python program to show the implementation of singly linked list# A linked list nodeclass Node: # Constructor to initialize a new node with data def __init__(self, new_data): self.data = new_data self.next = None# Function to print the linked listdef printList(head): # Loop that runs until head is None while head: # Printing current node data print(head.data, end=" ") # Moving to the next node in the list head = head.next print()# Driver codedef main(): # Create a hard-coded linked list: # 2 -> 3 -> 4 -> 5 -> 6 head = Node(2) head.next = Node(3) head.next.next = Node(4) head.next.next.next = Node(5) head.next.next.next.next = Node(6) # Printing the above list print("Linked List:", end=" ") printList(head)if __name__ == "__main__": main()

// C# program to show the implementation of singly linked// listusing System;// A linked list nodepublic class Node { public int data; public Node next; // Constructor to initialize a new node with data public Node(int new_data) { data = new_data; next = null; }}public class GfG { // Function to print the linked list public static void printList(Node head) { // Loop that runs until head is null while (head != null) { // Printing current node data Console.Write(" " + head.data); // Moving to the next node in the list head = head.next; } Console.WriteLine(); } // Driver code public static void Main(string[] args) { // Create a hard-coded linked list: // 2 -> 3 -> 4 -> 5 -> 6 Node head = new Node(2); head.next = new Node(3); head.next.next = new Node(4); head.next.next.next = new Node(5); head.next.next.next.next = new Node(6); // Printing the above list Console.Write("Linked List:"); printList(head); }}

// Javascript program to show the implementation of singly// linked list// A linked list nodeclass Node { // Constructor to initialize a new node with data constructor(new_data) { this.data = new_data; this.next = null; }}// Function to print the linked listfunction printList(head) { // Loop that runs until head is null while (head !== null) { // Printing current node data process.stdout.write(head.data + " "); // Moving to the next node in the list head = head.next; } console.log();}// Driver codefunction main() { // Create a hard-coded linked list: // 2 -> 3 -> 4 -> 5 -> 6 let head = new Node(2); head.next = new Node(3); head.next.next = new Node(4); head.next.next.next = new Node(5); head.next.next.next.next = new Node(6); // Printing the above list process.stdout.write("Linked List: "); printList(head);}main();

Linked List: 2 3 4 5 6

Linked List vs. Array:

Time Complexity Analysis of Linked List and Array:

Advantages of Linked List:

• Dynamic nature: Linked lists are used for dynamic memory allocation.
• Memory efficient: Memory consumption of a linked list is efficient as its size can grow or shrink dynamically according to our requirements, which means effective memory utilization hence, no memory wastage.
• Ease of Insertion and Deletion: Insertion and deletion of nodes are easily implemented in a linked list at any position.
• Implementation: For the implementation of stacks and queues and for the representation of trees and graphs.
• The linked list can be expanded in constant time.

Disadvantages of Linked List:

• Memory usage: The use of pointers is more in linked lists hence, complex and requires more memory.
• Accessing a node: Random access is not possible due to dynamic memory allocation.
• Search operation costly: Searching for an element is costly and requires O(n) time complexity.
• Traversing in reverse order: Traversing is more time-consuming and reverse traversing is not possible in singly linked lists.

Applications of Linked List:

Here are some of the applications of a linked list:

• Linear data structures such as stack, queue, and non-linear data structures such as hash maps, and graphs can be implemented using linked lists.
• Dynamic memory allocation: We use a linked list of free blocks.
• Implementation of graphs: Adjacency list representation of graphs is the most popular in that it uses linked lists to store adjacent vertices.
• In web browsers and editors, doubly linked lists can be used to build a forwards and backward navigation button.
• A circular doubly linked list can also be used for implementing data structures like Fibonacci heaps.

Frequently Asked Questions (FAQs) about Linked List:

1. What is linked list data structure?

Linked list are most commonly used to handle dynamic data elements. Linked list consists of nodes and a node consists of two fields one for storing data and other for keeping the reference of next node.

2. What is linked list example?

A linked list can be assumed as a garland that is made up of flowers. Similarly, a linked list is made up of nodes. Every flower in this particular garland is referred to as a node. In addition, each node points to the next node in this list, and it contains data (in this case, the type of flower).

3. Why do we need linked list data structure??

There are some important advantages to using linked lists over other linear data structures. This is unlike arrays, as they are resizable at runtime. Additionally, they can be easily inserted and deleted.

4. What are linked lists used for?

The linked list is a linear data structure that stores data in nodes. these nodes hold both the data and a reference to the next node in the list. Linked are very efficient at adding and removing nodes because of their simple structure.

5. What is the difference between array and linked list?

There are some following differences between them:

• Arrays are data structures containing similar data elements, whereas linked lists are non-primitive data structures containing unordered linked elements.
• In an array, elements are indexed, but in a linked list nodes are not indexed.
• Accessing an element array is fast if we know the position of an element in the array, while in the Linked list it takes linear time so, the Linked list is quite bit slower.
• Operations like insertion and deletion in arrays take a lot of time. Whereas, the performance of these operations is faster in Linked lists.
• Arrays are of fixed size and their size is static but Linked lists are dynamic and flexible and can expand and shrink their size.

6. Why is a linked list preferred over an array?

Following are the reason that linked lists are preferred over array

• Nodes in a linked array, insertions, and deletions can be done at any point in the list at a constant time.
• Arrays are of fixed size and their size is static but Linked lists are dynamic and flexible and can expand and shrink their size.
• Linked lists provide an efficient way of storing related data and performing basic operations such as insertion, deletion, and updating of information at the cost of extra space required for storing the address.
• Insertion and deletion operations in the linked list are faster as compared to the array.

7. Which is the best array or linked list?

There are some advantages and disadvantages to both arrays and linked lists when it comes to storing linear data of similar types.

Advantages of linked list over arrays:

• Dynamic size: Linked lists are dynamic and flexible and can expand and shrink their size
• Ease of Insertion/Deletion: Insertion and deletion operations in linked list are faster as compared to the array

Disadvantages of linked list over arrays:

• If the array is sorted we can apply binary search to search any element which takes O(log(n)) time. But even if the linked list is sorted we cannot apply binary search and the complexity of searching elements in the linked list is O(n).
• A linked list takes more memory as compared to the array because extra memory space is required for the pointer with each element in the linked list.

8. What are the limitations of linked list?

Following are some limitations of the linked list:

• The use of pointers is more in linked lists hence, complex and requires more memory.
• Random access is not possible due to dynamic memory allocation.
• Traversing is more time-consuming and reverse traversing is not possible in singly linked lists.
• Searching for an element is costly and requires O(n) time complexity.

9. Why insertion/deletion are faster in a linked list?

If any element is inserted/ deleted from the array, all the other elements after it will be shifted in memory this takes a lot of time whereas manipulation in Linked List is faster because we just need to manipulate the addresses of nodes, so no bit shifting is required in memory, and it will not take that much of time.

10. What is the difference between a singly and doubly linked list?

Following are some difference between single and double linked list.

Conclusion:

There are many advantages of the linked list compared to array, despite the fact that they solve the similar problem to arrays, we have also discussed the advantage, disadvantages, and its application, and we concluded the fact that we can use a linked list if we need the dynamic size of storage and list are good for adding and removing items quickly or for tasks that require sequence but are not suitable for querying or search elements in a large collection of data.

So, it becomes important that we should always keep in mind the positive and negative aspects of a data structure and how they relate to the problem you are trying to solve.

Related articles:

• Top 50 Problems on Linked List Data Structure asked in SDE Interviews
• Understanding the basics of Linked List
• SDE SHEET – A Complete Guide for SDE Preparation
• Amazon SDE Sheet – A Guide for Amazon SDE Interview Preparation
• Google Interview Preparation For Software Engineer – A Complete Guide
• 100 Days of Code – A Complete Guide For Beginners and Experienced