Linked List (Data Structures 2023)

A linked list is a linear data structure in which nodes store elements and each node contains a reference (or pointer) to the next node in the sequence. The last node usually points to a null reference or None, indicating that the list has come to an end.

Common Uses of Linked List

  • Dynamic Data Structures
  • Implementing Other Data Structures
  • Memory Management
  • Graphs and Trees
  • File Processing
  • Music Play List

Why to use Linked List

Using linked lists over other data structures, such as arrays, has several advantages. Some of the main reasons why linked lists are preferred in certain situations are as follows:

  1. Dynamic Size: Linked lists can grow and shrink dynamically during programme execution, unlike arrays, which have a fixed size. This makes linked lists more adaptable and efficient memory managers.
  2. Efficient Insertion and Deletion: Linked lists are efficient for inserting and deleting elements because they only require changing pointers, as opposed to arrays, which require element shifting. This makes linked lists an excellent choice for applications that require frequent element insertion or deletion.
  3. Easy to Implement: Because linked lists do not require contiguous memory allocation like arrays, they are relatively simple to implement. As a result, they are an excellent choice for beginners who are just learning data structures and algorithms.
  4. Versatility: Linked lists can be used to implement a wide range of data structures, including stacks, queues, trees, and graphs.

Operation of Linked List

Linked lists are a type of data structure composed of a series of nodes, each of which contains a data value and a pointer to the next node in the sequence. Here are some examples of common operations on a linked list:

  • Inserting a new element at the start of the list: This entails creating a new node, assigning it the desired data value, and updating the head pointer to point to the new node.
  • Inserting a list element at the end: This entails making a new node, setting its data value to the desired value, traversing the list to the last node, and updating its next pointer to point to the new node.
  • Inserting an element into the list at a specific index: This entails creating a new node, setting its data value to the desired value, traversing the list to find the node preceding the desired index, and updating the node’s next pointer to point to the new node.
  • Removing an element from the beginning of the list: Removing an element from the list’s beginning involves freeing the memory allocated for the first node, updating the head pointer to point to the next node, and returning the first node’s data value.
  • Removing an element from the end of the list: Removing an element from the list’s end requires traversing the list to find the second-to-last node, freeing the memory allocated for the last node, and updating its next pointer to point to null.
  • Searching for an element in the list: Searching for an element in a list entails traversing the list from beginning to end until the desired element is found, or until the list is exhausted.
  • Accessing an element by index: Accessing an element by index entails traversing the list from the start to the desired index and returning the data value of the node at that index.

Types of Linked List

There are mainly three types of linked list.

  1. Singly Linked List
  2. Doubly Linked List
  3. Circular Linked List

Singly Linked List

A singly linked list is also referred to as a linked list or simply a linked list. A singly linked list is so named because each node has only one pointer that points to the next node in the list.

A singly linked list with three nodes containing the data elements 2, 3, and 4 is shown below:

  +------+    +------+    +------+
  |  2   | -> |  3   | -> |  4   |
  +------+    +------+    +------+

Time Complexity

OperationTime Complexity
Accessing an element by indexO(n)
Inserting an element at the beginning of the listO(1)
Inserting an element at the end of the listO(n)
Inserting an element at a specific indexO(n)
Removing an element from the beginning of the listO(1)
Removing an element from the end of the listO(n)
Removing an element from a specific indexO(n)
Searching for an elementO(n)

Space Complexity

OperationSpace Complexity
Creating an empty listO(1)
Adding an element to the beginning of the listO(1)
Adding an element to the end of the listO(1)
Adding an element at a specific indexO(1)
Removing an element from the beginning of the listO(1)
Removing an element from the end of the listO(1)
Removing an element from a specific indexO(1)
Searching for an elementO(1)

Doubly Linked List

Each node in a doubly linked list contains a data value, a pointer to the next node, and a pointer to the previous node. This enables traversal in both forward and reverse directions.

The first node in a doubly linked list is called the head, and the last node is called the tail. Each middle-of-the-list node has a predecessor (the previous node) and a successor (the next node).

         +------+  <-->   +------+ <-->   +------+
None|  2   | <-->    |  3   | <-->   |  4   |None
          +------+           +------+           +------+

Time and Space Complexity

OperationTime ComplexitySpace Complexity
Accessing an element by indexO(n)O(1)
Searching for an elementO(n)O(1)
Inserting or deleting an element at the beginning or end of the listO(1)O(1)
Inserting or deleting an element at a specific indexO(n)O(1)

Circular Linked List

A circular linked list is one in which the tail node points to the head node rather than null, resulting in a loop. A circular linked list, in other words, is a linked list in which the last node points to the first node.

Each node in a circular linked list has a data value and a pointer to the next node. The pointer from the last node points to the first node, forming a loop. The first node is referred to as the head node, and the last node is referred to as the tail node.

Time and Space Complexity

OperationTime ComplexitySpace Complexity
Accessing an element by indexO(n)O(1)
Searching for an elementO(n)O(1)
Inserting or deleting an element at the beginning or end of the listO(1)O(1)
Inserting or deleting an element at a specific indexO(n)O(1)
Space for n elementsO(n)

Example

Palindrome Linked List

Leave a Comment