Stacks, Queues, and Linked Structures · Linked Structures

Linked List Operations

Students implement search, insert, delete, update, and reverse operations while handling empty, first-node, and last-node cases.

Enroll Now Text Us Contact Code Scholars Full DSA Course

Student Focus

We slow down edge cases so students build reliable pointer habits.

Guided Lesson Notes

Understanding Linked List Operations

Linked List Operations focuses on restricted access order and how items enter, wait, move, or leave a structure. Students implement search, insert, delete, update, and reverse operations while handling empty, first-node, and last-node cases.

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 Operations 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 Operations

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

Key Ideas

Insertion and deletion cases
Previous and current references
List reversal

Practice Prompts

Delete the first node matching a target.
Reverse a linked list and explain each reference change.

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 Operations

Trace a small input, focusing on insertion and deletion cases.

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

Complexity Check

Costs students should be able to explain

Operation	Typical Cost	Reason
Push/enqueue at supported end	O(1)	Stacks and queues are designed around restricted end operations.
Search for a value	O(n)	Finding an arbitrary item usually requires traversal.
Reference update	O(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 Operations 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

1Use a dummy node before the head to handle deleting the first node.
2Move a fast pointer k steps ahead.
3Move fast and slow together until fast reaches the final node.
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 Operations: 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 Session Text Us Open Online Compiler