Code ScholarsCodeScholars

Stacks, Queues, and Linked Structures · Linked Structures

Types of Linked List

Singly, doubly, and circular linked lists provide different navigation and update tradeoffs.

Enroll NowText UsContact Code ScholarsFull DSA Course

Student Focus

Students learn why extra references can simplify operations but increase bookkeeping.

Guided Lesson Notes

Understanding Types of Linked List

Types of Linked List focuses on restricted access order and how items enter, wait, move, or leave a structure. Singly, doubly, and circular linked lists provide different navigation and update tradeoffs.

The mental model is this: draw the structure as a line of items and mark the only legal places where an operation can touch it. That picture matters because it tells the student what information is available immediately and what must be searched, stored, or recomputed.

The core invariant is that after each operation, the front, back, top, head, tail, or current pointer must still describe the true structure. If a solution cannot state that rule, the code may still run on a sample input but fail on edge cases.

A strong implementation usually uses a small set of operations such as push, pop, peek, enqueue, dequeue, insert, remove, and traversal. The goal is not just to memorize an API; the goal is to know why each operation is allowed and what it costs.

In competitive programming, Types of Linked List tends to appear when the problem mentions undo, matching, next greater value, waiting order, recent history, or processing items in arrival order. Spotting that signal is often the difference between a nested-loop solution and an efficient one.

Visual Model

A small picture for Types of Linked List

front->A->B->C->back

Key Ideas

  • Singly linked lists
  • Doubly linked lists
  • Circular list behavior

Practice Prompts

  • Compare deletion with singly and doubly linked nodes.
  • Design a small circular playlist structure.

Vocabulary

Terms students should be able to say clearly

Top or front

The item that will be removed or inspected next.

Push or enqueue

An insertion operation with a rule about where the item goes.

Pop or dequeue

A removal operation with a rule about which item leaves.

Underflow

Trying to remove an item from an empty structure.

Pointer

A reference that connects nodes or tracks a position.

Traversal

Walking through items in the only order the structure allows.

Worked Example

Worked example: tracing Types of Linked List

Use a tiny input and focus on singly linked lists. The goal is to see how the topic changes state before scaling it to a full problem.

  1. 1Write a small input where Types of Linked List is clearly useful.
  2. 2Label the part of the input related to Singly linked lists.
  3. 3Perform one operation and explain which invariant is still true afterward.
  4. 4Run a second operation that touches an edge case, such as an empty side, duplicate value, boundary index, disconnected vertex, or tie.
  5. 5Finish by saying which operation dominates the runtime and why.

Complexity Check

Costs students should be able to explain

OperationTypical CostReason
Push/enqueue at supported endO(1)Stacks and queues are designed around restricted end operations.
Search for a valueO(n)Finding an arbitrary item usually requires traversal.
Reference updateO(1)Linked structures can change local links quickly once the position is known.

Common Mistakes

What to watch while practicing

  • Coding before drawing the structure or state changes.
  • Forgetting the invariant that makes the algorithm correct.
  • Testing only the sample input and skipping boundary cases.
  • Giving Big-O without explaining which operation dominates the work.

Interview-Style Coding Problem

Types of Linked List interview problem: Remove Nth Node From the End

Interview medium

Problem

Given a linked list and an integer k, remove the kth node from the end and print the resulting list.

Input

The first line contains n. The second line contains n node values. The third line contains k.

Output

Print the list after deletion, or EMPTY if no nodes remain.

Sample Input

5
1 2 3 4 5
2

Sample Output

1 2 3 5

Why the sample works

The second node from the end is 4, so it is removed.

Approach

  1. 1Use a dummy node before the head to handle deleting the first node.
  2. 2Move a fast pointer k steps ahead.
  3. 3Move fast and slow together until fast reaches the final node.
  4. 4Delete slow.next.

O(n) time and O(1) extra pointer space.

Java Solution

import java.util.*;

public class Main {
  static class ListNode {
    int val;
    ListNode next;
    ListNode(int val) {
      this.val = val;
    }
  }

  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int n = sc.nextInt();

    ListNode dummy = new ListNode(0);
    ListNode tail = dummy;
    for (int i = 0; i < n; i++) {
      tail.next = new ListNode(sc.nextInt());
      tail = tail.next;
    }

    int k = sc.nextInt();
    ListNode fast = dummy;
    ListNode slow = dummy;

    for (int i = 0; i < k; i++) {
      fast = fast.next;
    }

    while (fast.next != null) {
      fast = fast.next;
      slow = slow.next;
    }

    slow.next = slow.next.next;

    ListNode cur = dummy.next;
    if (cur == null) {
      System.out.println("EMPTY");
      return;
    }

    boolean first = true;
    while (cur != null) {
      if (!first) System.out.print(" ");
      System.out.print(cur.val);
      first = false;
      cur = cur.next;
    }
    System.out.println();
  }
}

Python Solution

class Node:
    def __init__(self, val):
        self.val = val
        self.next = None

n = int(input())
values = list(map(int, input().split()))
k = int(input())

dummy = Node(0)
tail = dummy
for value in values:
    tail.next = Node(value)
    tail = tail.next

fast = dummy
slow = dummy
for _ in range(k):
    fast = fast.next

while fast.next:
    fast = fast.next
    slow = slow.next

slow.next = slow.next.next

answer = []
cur = dummy.next
while cur:
    answer.append(cur.val)
    cur = cur.next

if answer:
    print(*answer)
else:
    print("EMPTY")

Practice Challenge

Make the idea your own

Create a two-minute explanation of Types of Linked List: define it, trace one example, name one edge case, and give the runtime of the main operation.

Tutoring Connection

Turn the topic into usable problem-solving skill

Students can use this page before a lesson, after a difficult homework assignment, or while preparing for AP Computer Science A extensions, Advanced Topics in CS, USACO growth, or a college data structures course.

Schedule Free ConsultationText UsOpen Online Compiler