Types of Linked List in Data Structures

Q: How many types of linked lists are there?

There are four main types: singly, doubly, circular singly and circular doubly linked lists. They differ in how many links each node has and whether the last node connects back to the first.

Q: How do you know when to stop traversing a circular linked list?

There is no null at the end, so stop when you come back to the node you started from:

Q: What is a circular doubly linked list?

It is a doubly linked list where the last node's next points to the head and the head's prev points to the last node. You can move in both directions forever, and the tail is reachable from the head in O(1) through head.prev.

Q: Which type would you use for a music playlist with repeat mode?

A circular doubly linked list: the circular link restarts the playlist after the last song, and the prev links support the previous-track button.

Q: Write Java code to convert a singly linked list into a circular one.

Java example: static void makeCircular(Node head) { if (head == null) { return; } Node current = head; while (current.next != null) { current = current.next; } current.next = head; // last node now points to the first }

Q: Write Java code to check whether a linked list is circular.

This assumes the list either ends in null or loops back to the head. For a list that loops back to a middle node, use Floyd's cycle detection instead.

Q: What is a header (sentinel) linked list?

A header linked list starts with a special dummy node that holds no real data. Because the list always has at least one node, inserting or deleting at the front no longer needs special code for an empty list.

Q: Why does a circular linked list often keep a tail reference instead of a head?

With a reference to the tail, both ends are reachable in O(1): the tail itself, and the head through tail.next. That makes inserting at both the beginning and the end O(1).

Q: Which linked list type is used for the adjacency list of a graph?

Usually a singly linked list (or in Java, an ArrayList ) per vertex. Each list only needs to be traversed forward to find the neighbours, so the extra prev link of a doubly linked list would waste memory.

Types of Linked List in Data Structures

A Linked List is a linear data structure that consists of a collection of elements; each element in a linked list is called a Node. The node contains two parts: the first part contains data, and the second part contains the address of the next node.

Types of Linked Lists in Data Structures

There are mainly three types of linked lists in data structures as given below:

1. Singly Linked List

A Singly Linked List is a linear (ordered) data structure that contains a collection of elements, and each element is connected to its next element in a sequence.

Each element in a singly linked list is called a Node. The node consists of two fields: a data field and the reference field (address of the next node).

There is a HEAD pointer, which points to the first node of the singly linked list, and if the list is empty, then it stores NULL and the last node is called the Tail, and it stores NULL in the reference field (next).

A singly linked list can traverse only in the forward direction because each node contains the address of the next node.

2. Doubly Linked List

A doubly linked list is a linear data structure; it is another form of Linked List.

A doubly linked list is a collection of seqential nodes (elements); each node consists of three fields: two pointer fields (references to the previous and to the next node in the sequence of nodes) and one data field.

A double linked list can be traversed in forward and backward directions because each node has two pointers, previous and next.

In the Doubly Linked List, each node consist of three parts:

First Part: Pointer to point the previous node in the list.
Second Part: The data (value) stored in the node.
Third Part: Pointer to point the next node in the list.

Circular Linked List

A circular linked list is another type of linked list where the last node points to the first node of the list, creating a circular structure. Unlike a normal linked list, a circular linked list does not have a NULL pointer at the end.

As with other linked lists, circular linked lists can also grow or shrink dynamically as elements are added or removed.

Frequently Asked Questions (FAQ)

Q1. How many types of linked lists are there?

There are four main types: singly, doubly, circular singly and circular doubly linked lists. They differ in how many links each node has and whether the last node connects back to the first.

Q2. How is a circular linked list different from the other types?

In a circular linked list, the last node points back to the first node instead of null. You can start at any node and reach every other node, which is useful for round-robin scheduling and repeating playlists.

Q3. How do you know when to stop traversing a circular linked list?

There is no null at the end, so stop when you come back to the node you started from:

PrintCircular.java

static void printCircular(Node head) {
    if (head == null) {
        return;
    }
    Node current = head;
    do {
        System.out.print(current.data + " ");
        current = current.next;
    } while (current != head);
}

Q4. What is a circular doubly linked list?

It is a doubly linked list where the last node's next points to the head and the head's prev points to the last node. You can move in both directions forever, and the tail is reachable from the head in O(1) through head.prev.

Q5. Which type would you use for a music playlist with repeat mode?

A circular doubly linked list: the circular link restarts the playlist after the last song, and the prev links support the previous-track button.

Q6. Write Java code to convert a singly linked list into a circular one.

MakeCircular.java

static void makeCircular(Node head) {
    if (head == null) {
        return;
    }
    Node current = head;
    while (current.next != null) {
        current = current.next;
    }
    current.next = head;    // last node now points to the first
}

Q7. Write Java code to check whether a linked list is circular.

IsCircular.java

static boolean isCircular(Node head) {
    if (head == null) {
        return true;              // an empty list is usually treated as circular
    }
    Node current = head.next;
    while (current != null && current != head) {
        current = current.next;
    }
    return current == head;
}

This assumes the list either ends in null or loops back to the head. For a list that loops back to a middle node, use Floyd's cycle detection instead.

Q8. What is a header (sentinel) linked list?

A header linked list starts with a special dummy node that holds no real data. Because the list always has at least one node, inserting or deleting at the front no longer needs special code for an empty list.

Q9. Why does a circular linked list often keep a tail reference instead of a head?

With a reference to the tail, both ends are reachable in O(1): the tail itself, and the head through tail.next. That makes inserting at both the beginning and the end O(1).

Q10. Which linked list type is used for the adjacency list of a graph?

Usually a singly linked list (or in Java, an ArrayList) per vertex. Each list only needs to be traversed forward to find the neighbours, so the extra prev link of a doubly linked list would waste memory.

Was this tutorial helpful?

Help Us Improve

Types of Linked List in Data Structures

Types of Linked Lists in Data Structures

1. Singly Linked List

2. Doubly Linked List

Circular Linked List

Frequently Asked Questions (FAQ)