Linked Lists

A Linked List is a linear data structure where elements are not stored at contiguous memory locations but are linked using pointers. Each element, known as a node, consists of two parts: the data and a reference (link) to the next node in the sequence. This allows for efficient insertions and deletions, as you only need to update the references of the nodes and not move entire sections of data around. However, this also means that access times can be slow as you have to traverse the list from the head node to find the element you want. Linked lists are used in many data structures and algorithms, like stacks, queues, graphs, and hash tables.

Types of Linked Lists

There are four types of Linked Lists:

  • Singly Linked List: It is the simplest type of linked list, where each node contains some data and a pointer to the next node of the same data type. This allows traversal of data only in one direction.

  • Doubly Linked List: A more complex type of linked list that contains a pointer to the next as well as the previous node in sequence. This enables us to traverse the list in both forward and backward directions.

  • Circular Linked List: In this type of linked list, the last node points back to the first node, making a circular loop.

  • Doubly Circular Linked List: This is a more complex type of linked list where the last node points back to the first node and the first node also points to the last node, making it circular. Also, each node has a pointer to its next and previous node, making it doubly linked.

Example

// Singly Linked List:
public class Node
{
    public int data;
    public Node next;

    public Node(int i)
    {
        this.data = i;
        this.next = null;
    }
}

var list = new SinglyLinkedList();

Operations of the Linked Lists in data structure

There are some operations of the Linked Lists in the data structure:

  • Traversal: Access each element of the linked list.

  • Insertion: Adds a new node to the linked list. You can add elements to either the beginning, middle or end of the linked list.

  • Deletion: Removes an existing node from the linked list. You can delete either from the beginning, end or from a particular position.

  • Search: Finds a particular node in the linked list.

  • Update: Modifies the value of a node.

  • Sort: Arranges nodes in a specific order.

Complexity Table

OperationBest CaseAverage CaseWorst Case

Access

O(N)

O(N)

O(N)

Search

O(N)

O(N)

O(N)

Insertion (at the beginning)

O(1)

O(1)

O(1)

Insertion (at the end, with a tail pointer)

O(1)

O(1)

O(1)

Insertion (at the end, without a tail pointer)

O(N)

O(N)

O(N)

Insertion (in the middle)

O(N)

O(N)

O(N)

Deletion (from the beginning)

O(1)

O(1)

O(1)

Deletion (from the end, with a tail pointer)

O(N)

O(N)

O(N)

Deletion (from the end, without a tail pointer)

O(N)

O(N)

O(N)

Deletion (from the middle)

O(N)

O(N)

O(N)

Update

O(N)

O(N)

O(N)

PreviousArrayNextStacks

Last updated