Skip to main content
Code ScholarsCodeScholars

Stacks, Queues, and Linked Structures · Linked Structures

Linked List

Linked lists store data in nodes connected by references, which makes insertion flexible but random access slower.

Enroll NowText UsContact Code ScholarsFull DSA Course

Student Focus

Students practice diagrams first because linked-list bugs are usually reference bugs.

Guided Lesson Notes

Understanding Linked List

Linked List focuses on restricted access order and how items enter, wait, move, or leave a structure. Linked lists store data in nodes connected by references, which makes insertion flexible but random access slower.

Model: draw the structure as a line of items and mark the only legal places where an operation can touch it.

Invariant: after each operation, the front, back, top, head, tail, or current pointer must still describe the true structure.

Implementation: a small set of operations such as push, pop, peek, enqueue, dequeue, insert, remove, and traversal.

Use Linked List when the problem mentions undo, matching, next greater value, waiting order, recent history, or processing items in arrival order.

Visual Model

A small picture for Linked List

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

Key Ideas

  • Nodes and references
  • Head and tail pointers
  • Sequential traversal

Practice Prompts

  • Draw a list before and after an insertion.
  • Implement contains and size by walking node references.

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 Linked List

Trace a small input, focusing on nodes and references.

  1. 1Write a small input where Linked List is clearly useful.
  2. 2Label the part of the input related to Nodes and references.
  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

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 Linked List: define it, trace one example, name one edge case, and give the runtime of the main operation.

Tutoring Connection

Need help with this topic?

Bring a question or code attempt to a tutoring session.

Reserve a Free SessionText UsOpen Online Compiler