Skip to main content

LinkedList

A singly linked list implementation that provides efficient operations for adding and removing elements, especially at the beginning and end.

Installation​

npm install @msnkr/data-structures

Usage​

import { LinkedList } from '@msnkr/data-structures';

const list = new LinkedList<number>();

API Reference​

Properties​

  • size: number - Number of elements in the list
  • isEmpty(): boolean - Whether the list is empty

Methods​

Adding Elements​

// Add to end - O(1)
list.append(1);

// Add to start - O(1)
list.prepend(0);

// Insert at specific position - O(n)
list.insertAt(2, 1);
Performance

Insertions at the beginning and end are O(1) constant time.

Removing Elements​

// Remove from start - O(1)
const first = list.removeFirst();

// Remove at specific position - O(n)
const element = list.removeAt(1);

// Remove first occurrence of value - O(n)
const removed = list.remove(42);

Accessing Elements​

// Get element at position - O(n)
const element = list.get(0);

// Find position of element - O(n)
const index = list.indexOf(42);

// Check if element exists - O(n)
const exists = list.contains(42);

Utility Methods​

// Convert to array - O(n)
const array = list.toArray();

// Remove all elements - O(1)
list.clear();

Iteration​

const list = new LinkedList<string>();
list.append('a');
list.append('b');

// Forward iteration
for (const value of list) {
  console.log(value);
}

Examples​

Basic Usage​

const list = new LinkedList<number>();

// Add elements
list.append(1); // [1]
list.append(2); // [1, 2]
list.prepend(0); // [0, 1, 2]

console.log(list.toArray()); // [0, 1, 2]
console.log(list.size); // 3

Building a Task List​

const tasks = new LinkedList<string>();

// Add tasks
tasks.append('Review PRs');
tasks.append('Write tests');
tasks.prepend('Morning standup'); // High priority

// Process tasks in order
while (!tasks.isEmpty()) {
  const task = tasks.removeFirst();
  console.log(`Processing: ${task}`);
}

Error Handling​

import {
  EmptyStructureError,
  IndexOutOfBoundsError,
} from '@msnkr/data-structures';

try {
  const empty = new LinkedList<number>();
  empty.removeFirst(); // Throws EmptyStructureError
} catch (error) {
  if (error instanceof EmptyStructureError) {
    console.log('List is empty!');
  }
}

try {
  const list = new LinkedList<number>();
  list.append(1);
  list.get(10); // Throws IndexOutOfBoundsError
} catch (error) {
  if (error instanceof IndexOutOfBoundsError) {
    console.log('Index out of range!');
  }
}
Error Conditions
  • removeFirst() throws EmptyStructureError on empty list
  • get(), insertAt(), removeAt() throw IndexOutOfBoundsError for invalid indices

Performance Characteristics​

OperationTime ComplexityDescription
append()O(1)Add element to end
prepend()O(1)Add element to start
insertAt()O(n)Insert at specific position
removeFirst()O(1)Remove element from start
removeAt()O(n)Remove at specific position
remove()O(n)Remove first occurrence
get()O(n)Access element at position
indexOf()O(n)Find position of element
contains()O(n)Search for element
clear()O(1)Remove all elements
toArray()O(n)Convert to array

Space Complexity: O(n) where n is the number of elements

Implementation Details​

Internal Structure​

  • Uses a singly linked node structure
  • Maintains both head and tail pointers for O(1) append
  • Each node contains a value and next pointer
When to Use LinkedList

Perfect for:

  • Frequent insertions/deletions at the beginning
  • Forward-only traversal
  • When memory overhead of doubly linked list isn't needed
  • Building queues, stacks, or simple lists
When to Avoid

Consider alternatives when:

  • Random access is frequent → Use Array
  • Bidirectional traversal needed → Use DoublyLinkedList
  • Memory is extremely constrained → Use Array

See Also​

Examples:

Related Data Structures:

  • DoublyLinkedList - Bidirectional linked list with reverse iteration
  • Queue - First-In-First-Out (FIFO) queue
  • Deque - Double-ended queue