707. Design Linked List

At a Glance

Topic: system-design-coding
Pattern: Linked list ops with sentinel
Difficulty: Medium
Companies: Amazon, Microsoft, Bloomberg, LinkedIn, Adobe
Frequency: Medium
LeetCode: 707

Problem (one-liner)

Implement a singly linked list class supporting indexed insert/delete/get at head/tail with correct bounds checking (-1 when invalid).

Recognition Cues

Index-based API on singly linked list — walk from sentinel head
Dummy head simplifies edge cases

Diagram

At-a-glance flow (replace with problem-specific Mermaid as you refine this note). camelCase node IDs; no spaces in IDs.

Loading diagram…

Approaches

Optimal — struct node{value, next} and sentinel *node with size counter — O(index) per op.

Optimal Solution

Go

package main

type listNode struct {
	value int
	next  *listNode
}

// MyLinkedList API:
// - Constructor()
// - int get(index int)
// - void addAtHead(val int)
// - void addAtTail(val int)
// - void addAtIndex(index int, val int)
// - void deleteAtIndex(index int)

type MyLinkedList struct {
	sentinel *listNode
	size     int
}

func Constructor() MyLinkedList {
	return MyLinkedList{sentinel: &listNode{}}
}

func (list *MyLinkedList) Get(index int) int {
	if index < 0 || index >= list.size {
		return -1
	}
	current := list.sentinel.next
	for step := 0; step < index; step++ {
		current = current.next
	}
	return current.value
}

func (list *MyLinkedList) AddAtHead(value int) {
	list.AddAtIndex(0, value)
}

func (list *MyLinkedList) AddAtTail(value int) {
	list.AddAtIndex(list.size, value)
}

func (list *MyLinkedList) AddAtIndex(index int, value int) {
	if index < 0 || index > list.size {
		return
	}
	previous := list.sentinel
	for step := 0; step < index; step++ {
		previous = previous.next
	}
	previous.next = &listNode{value: value, next: previous.next}
	list.size++
}

func (list *MyLinkedList) DeleteAtIndex(index int) {
	if index < 0 || index >= list.size {
		return
	}
	previous := list.sentinel
	for step := 0; step < index; step++ {
		previous = previous.next
	}
	previous.next = previous.next.next
	list.size--
}

JavaScript

class ListNode {
	constructor(value = 0, next = null) {
		this.value = value;
		this.next = next;
	}
}

class MyLinkedList {
	constructor() {
		this.sentinel = new ListNode();
		this.size = 0;
	}

	get(index) {
		if (index < 0 || index >= this.size) {
			return -1;
		}
		let current = this.sentinel.next;
		for (let step = 0; step < index; step++) {
			current = current.next;
		}
		return current.value;
	}

	addAtHead(value) {
		this.addAtIndex(0, value);
	}

	addAtTail(value) {
		this.addAtIndex(this.size, value);
	}

	addAtIndex(index, value) {
		if (index < 0 || index > this.size) {
			return;
		}
		let previous = this.sentinel;
		for (let step = 0; step < index; step++) {
			previous = previous.next;
		}
		previous.next = new ListNode(value, previous.next);
		this.size++;
	}

	deleteAtIndex(index) {
		if (index < 0 || index >= this.size) {
			return;
		}
		let previous = this.sentinel;
		for (let step = 0; step < index; step++) {
			previous = previous.next;
		}
		previous.next = previous.next.next;
		this.size--;
	}
}