Singly Linked List

dynamicsequentialpointer

Press play to start

1class ListNode { constructor(public val: number, public next: ListNode | null = null) {} }
2let head: ListNode | null = null
3function insertAtHead(val: number) {
4  head = new ListNode(val, head)
5}
6function traverse() {
7  let cur = head
8  while (cur) { console.log(cur.val); cur = cur.next }
9}
10function deleteVal(val: number) {
11  if (!head) return
12  if (head.val === val) { head = head.next; return }
13  let cur = head
14  while (cur.next && cur.next.val !== val) cur = cur.next
15  if (cur.next) cur.next = cur.next.next
16}

Step 1/0

Complexity

Best:O(1)
Average:O(n)
Worst:O(n)
Space:O(n)

Description

A sequence of nodes where each node stores a value and a pointer to the next node. Allows efficient insertion and deletion at any point.

When to use

When frequent insertions/deletions are needed and random access is not required. Foundation for stacks, queues, and hash table chaining.