Linked List

Space	Time
	Access	Lookup	Insertion	Deletion
O(n)	O(n)	O(n)	O(1)	O(1)

Definition

Short

Linked List is a dynamic data structure that consists of nodes, each containing data and a reference to the next node in the sequence.

Simplified

Linked List is like a treasure hunt game. You start at the 'head' node and follow links to other nodes, each holding data and a link to the next node. The last node, or 'tail', has no link. Just like the game, you traverse the list to find your 'treasure' or data.

Detailed

Linked list is a dynamic structure organizing elements linearly via pointers, not physical memory locations like arrays. Each element, or node, holds data and a link to the next node. This allows efficient element addition or deletion during iteration. Advanced linked lists have extra links for efficient element insertion or removal from any reference point. However, linked lists have linear access time, making operations like random access challenging. While arrays have better cache locality, the flexibility of linked lists makes them useful in many computer science areas.

Variants

Singly-Linked List

Linear data structure where elements, each containing data and a reference to the next element, form a sequence. It begins with a head node, and the last node has a null reference. Singly-linked lists are useful for dynamic memory allocation.

Doubly Linked List

Linear data structure where nodes contain data and 2 pointers, one pointing to the next node and another to the previous node, allowing for bidirectional traversal.

Circular Linked List

Variation of a Linked List where the last node points back to the first, forming a closed loop. It facilitates continuous traversal and is useful for scenarios requiring repetitive processing or indefinite iteration through a sequence.

Doubly Circular Linked List

Data structure where each node has data, a pointer to the next node, and a pointer to the previous node, forming bidirectional links. The last node connects back to the first, creating a closed loop. This structure enables both forward and backward traversal and is useful for scenarios requiring bidirectional navigation with continuous iteration.

Practice

Practice

Aspect	Pseudo Code
Prepend	prepend(data) node = Node(data, head) head = node
Insert Before	insert_before(value, data) if head == ø: return if data.head == value: node = Node(data, head) head = node return current = head while current.next != ø and current.next.data != value: current = current.next if current.next != ø: current.next = Node(data, current.next)
Insert After	insert_after(value, data) current = head while current != ø and current.data != value: current = current.next if current != ø: current.next = Node(data, current.next)
Insert at Index	insert_at(index, data) if index < 0: throw error "Index must be greater than or equal to 0" if index == 0: node = Node(data, head) head = node return current = head current_index = 0 while current != ø and index - 1 > current_index: current = current.next current_index++ if current == ø: throw error "Index exceeds the size of the list" current.next = Node(data, current.next)
Append	append(data) if head == ø: head = Node(data) else: current = head while current.next != ø: current = current.next current.next = Node(data)
Find	find(value) current = head while current != ø and current.data != value: current = current.next return current.data
Delete Head	delete_head() if head != ø: head = head.next
Remove Node	delete(value) if head == ø: return if head.data == value: head = head.next return current = head while current.next != ø and current.next.data != value: current = current.next if current.next != ø: current.next = current.next.next
Delete Tail	delete_last() if head == ø: return if head.next == ø: head = ø return current = head while current.next.next != ø: current = current.next current.next = ø
Reverse	reverse() prev = ø current = head while current != ø: next = current.next current.next = prev prev = current current = next head = prev
Traverse	traverse() current = head while current != ø: yield current.data current = current.next

Solution

package main

type Node struct {
	data interface{}
	next *Node
}

type LinkedList struct {
	head *Node
}

func (l *LinkedList) prepend(data interface{}) {
	l.head = &Node{data: data, next: l.head}
}

func (l *LinkedList) insertBefore(value interface{}, data interface{}) {
	if l.head == nil {
		return
	}

	if l.head.data == value {
		l.head = &Node{data: data, next: l.head}
		return
	}

	current := l.head
	for current.next != nil && current.next.data != value {
		current = current.next
	}

	if current.next != nil {
		current.next = &Node{data: data, next: current.next}
	}
}

func (l *LinkedList) insertAfter(value interface{}, data interface{}) {
	current := l.head
	for current != nil && current.data != value {
		current = current.next
	}

	if current != nil {
		current.next = &Node{data: data, next: current.next}
	}
}

func (l *LinkedList) insertAt(index int, data interface{}) {
	if index < 0 {
		panic("Index must be greater than or equal to 0")
	}

	if index == 0 {
		l.head = &Node{data: data, next: l.head}
		return
	}

	current := l.head
	currentIndex := 0
	for current != nil && currentIndex < index-1 {
		current = current.next
		currentIndex++
	}

	if current == nil {
		panic("Index exceeds the size of the list")
	}

	current.next = &Node{data: data, next: current.next}
}

func (l *LinkedList) append(data interface{}) {
	if l.head == nil {
		l.head = &Node{data: data}
	} else {
		current := l.head
		for current.next != nil {
			current = current.next
		}
		current.next = &Node{data: data}
	}
}

func (l *LinkedList) find(value interface{}) *Node {
	current := l.head
	for current != nil && current.data != value {
		current = current.next
	}
	return current
}

func (l *LinkedList) deleteHead() {
	if l.head != nil {
		l.head = l.head.next
	}
}

func (l *LinkedList) delete(value interface{}) {
	if l.head == nil {
		return
	}

	if l.head.data == value {
		l.head = l.head.next
		return
	}

	current := l.head
	for current.next != nil && current.next.data != value {
		current = current.next
	}

	if current.next != nil {
		current.next = current.next.next
	}
}

func (l *LinkedList) deleteLast() {
	if l.head == nil {
		return
	}

	if l.head.next == nil {
		l.head = nil
		return
	}

	current := l.head
	for current.next.next != nil {
		current = current.next
	}
	current.next = nil
}

func (l *LinkedList) reverse() {
	var prev *Node
	current := l.head
	var next *Node
	for current != nil {
		next = current.next
		current.next = prev
		prev = current
		current = next
	}
	l.head = prev
}

func (l *LinkedList) traverse() {
	current := l.head
	for current != nil {
		fmt.Println(current.data)
		current = current.next
	}
}

public class LinkedList<T> {

  private Node<T> head = null;

  public void prepend(T data) {
    head = new Node<>(data, head);
  }

  public void insertBefore(T value, T data) {
    if (head == null) {
      return;
    }

    if (head.data.equals(value)) {
      head = new Node<>(data, head);
      return;
    }

    Node<T> current = head;
    while (current.next != null && !current.next.data.equals(value)) {
      current = current.next;
    }

    if (current.next != null) {
      current.next = new Node<>(data, current.next);
    }
  }

  public void insertAfter(T value, T data) {
    Node<T> current = head;
    while (current != null && !current.data.equals(value)) {
      current = current.next;
    }

    if (current != null) {
      current.next = new Node<>(data, current.next);
    }
  }

  public void insertAt(int index, T data) {
    if (index < 0) {
      throw new IndexOutOfBoundsException("Index must be greater than or equal to 0");
    }

    if (index == 0) {
      head = new Node<>(data, head);
      return;
    }

    Node<T> current = head;
    int currentIndex = 0;
    while (current != null && currentIndex < index - 1) {
      current = current.next;
      currentIndex++;
    }

    if (current == null) {
      throw new IndexOutOfBoundsException("Index exceeds the size of the list");
    }

    current.next = new Node<>(data, current.next);
  }

  public void append(T data) {
    if (head == null) {
      head = new Node<>(data);
    } else {
      Node<T> current = head;
      while (current.next != null) {
        current = current.next;
      }
      current.next = new Node<>(data);
    }
  }

  public T find(T value) {
    Node<T> current = head;
    while (current != null && !current.data.equals(value)) {
      current = current.next;
    }
    return current != null ? current.data : null;
  }

  public void deleteHead() {
    if (head != null) {
      head = head.next;
    }
  }

  public void delete(T value) {
    if (head == null) {
      return;
    }

    if (head.data.equals(value)) {
      head = head.next;
      return;
    }

    Node<T> current = head;
    while (current.next != null && !current.next.data.equals(value)) {
      current = current.next;
    }

    if (current.next != null) {
      current.next = current.next.next;
    }
  }

  public void deleteLast() {
    if (head == null) {
      return;
    }

    if (head.next == null) {
      head = null;
      return;
    }

    Node<T> current = head;
    while (current.next.next != null) {
      current = current.next;
    }

    current.next = null;
  }

  public void reverse() {
    Node<T> prev = null;
    Node<T> current = head;
    Node<T> next;
    while (current != null) {
      next = current.next;
      current.next = prev;
      prev = current;
      current = next;
    }
    head = prev;
  }

  public void traverse() {
    Node<T> current = head;
    while (current != null) {
      System.out.println(current.data);
      current = current.next;
    }
  }

  private class Node<T> {

    T data;
    Node<T> next;

    Node(T data) {
      this.data = data;
    }

    Node(T data, Node<T> next) {
      this.data = data;
      this.next = next;
    }
  }
}

class Node {
  constructor(data, next = null) {
    this.data = data;
    this.next = next;
  }
}

class LinkedList {
  constructor() {
    this.head = null;
  }

  prepend(data) {
    this.head = new Node(data, this.head);
  }

  insertBefore(value, data) {
    if (this.head === null) {
      return;
    }

    if (this.head.data === value) {
      this.head = new Node(data, this.head);
      return;
    }

    let current = this.head;
    while (current.next !== null && current.next.data !== value) {
      current = current.next;
    }

    if (current.next !== null) {
      current.next = new Node(data, current.next);
    }
  }

  insertAfter(value, data) {
    let current = this.head;
    while (current !== null && current.data !== value) {
      current = current.next;
    }

    if (current !== null) {
      current.next = new Node(data, current.next);
    }
  }

  insertAt(index, data) {
    if (index < 0) {
      throw new Error("Index must be greater than or equal to 0");
    }

    if (index === 0) {
      this.head = new Node(data, this.head);
      return;
    }

    let current = this.head;
    let currentIndex = 0;
    while (current !== null && currentIndex < index - 1) {
      current = current.next;
      currentIndex++;
    }

    if (current === null) {
      throw new Error("Index exceeds the size of the list");
    }

    current.next = new Node(data, current.next);
  }

  append(data) {
    if (this.head === null) {
      this.head = new Node(data);
    } else {
      let current = this.head;
      while (current.next !== null) {
        current = current.next;
      }
      current.next = new Node(data);
    }
  }

  find(value) {
    let current = this.head;
    while (current !== null && current.data !== value) {
      current = current.next;
    }
    return current ? current.data : null;
  }

  deleteHead() {
    if (this.head !== null) {
      this.head = this.head.next;
    }
  }

  deleteNode(value) {
    if (this.head === null) {
      return;
    }

    if (this.head.data === value) {
      this.head = this.head.next;
      return;
    }

    let current = this.head;
    while (current.next !== null && current.next.data !== value) {
      current = current.next;
    }

    if (current.next !== null) {
      current.next = current.next.next;
    }
  }

  deleteLast() {
    if (this.head === null) {
      return;
    }

    if (this.head.next === null) {
      this.head = null;
      return;
    }

    let current = this.head;
    while (current.next.next !== null) {
      current = current.next;
    }

    current.next = null;
  }

  reverse() {
    let prev = null;
    let current = this.head;
    let next = null;
    while (current !== null) {
      next = current.next;
      current.next = prev;
      prev = current;
      current = next;
    }
    this.head = prev;
  }

  traverse() {
    let current = this.head;
    while (current !== null) {
      console.log(current.data);
      current = current.next;
    }
  }
}

class LinkedList<T> {
    class Node<T>(var data: T, var next: Node<T>? = null)

    private var head: Node<T>? = null

    fun prepend(data: T) {
        head = Node(data, head)
    }

    fun insertBefore(value: T, data: T) {
        if (head == null) {
            return
        }

        if (head?.data == value) {
            head = Node(data, head)
            return
        }

        var current = head
        while (current?.next != null && current.next?.data != value) {
            current = current.next
        }

        if (current?.next != null) {
            current.next = Node(data, current.next)
        }
    }

    fun insertAfter(value: T, data: T) {
        var current = head
        while (current != null && current.data != value) {
            current = current.next
        }

        if (current != null) {
            current.next = Node(data, current.next)
        }
    }

    fun insertAt(index: Int, data: T) {
        if (index < 0) {
            throw IndexOutOfBoundsException("Index must be greater than or equal to 0")
        }

        if (index == 0) {
            head = Node(data, head)
            return
        }

        var current = head
        var currentIndex = 0
        while (current != null && currentIndex < index - 1) {
            current = current.next
            currentIndex++
        }

        if (current == null) {
            throw IndexOutOfBoundsException("Index exceeds the size of the list")
        }

        current.next = Node(data, current.next)
    }

    fun append(data: T) {
        if (head == null) {
            head = Node(data)
        } else {
            var current = head
            while (current?.next != null) {
                current = current.next
            }
            current?.next = Node(data)
        }
    }

    fun find(value: T): Node<T>? {
        var current = head
        while (current != null && current.data != value) {
            current = current.next
        }
        return current?.data
    }

    fun deleteHead() {
        if (head != null) {
            head = head?.next
        }
    }

    fun delete(value: T) {
        if (head == null) {
            return
        }

        if (head?.data == value) {
            head = head?.next
            return
        }

        var current = head
        while (current?.next != null && current.next?.data != value) {
            current = current.next
        }

        if (current?.next != null) {
            current.next = current.next?.next
        }
    }

    fun deleteLast() {
        if (head == null) {
            return
        }

        if (head?.next == null) {
            head = null
            return
        }

        var current = head
        while (current?.next?.next != null) {
            current = current.next
        }

        current?.next = null
    }

    fun reverse() {
        var prev: Node<T>?
        var current = head
        var next: Node<T>?
        while (current != null) {
            next = current.next
            current.next = prev
            prev = current
            current = next
        }
        head = prev
    }

    fun traverse() {
        var current = head
        while (current != null) {
            println(current.data)
            current = current.next
        }
    }
}

class LinkedList:
    class Node:
        def __init__(self, data, next=None):
            self.data = data
            self.next = next

    def __init__(self):
        self.head = None

    def prepend(self, data):
        self.head = self.Node(data, self.head)

    def insert_before(self, value, data):
        if self.head is None:
            return

        if self.head.data == value:
            self.head = self.Node(data, self.head)
            return

        current = self.head
        while current.next is not None and current.next.data != value:
            current = current.next

        if current.next is not None:
            current.next = self.Node(data, current.next)

    def insert_after(self, value, data):
        current = self.head
        while current is not None and current.data != value:
            current = current.next

        if current is not None:
            current.next = self.Node(data, current.next)

    def insert_at(self, index, data):
        if index < 0:
            raise IndexError("Index must be greater than or equal to 0")

        if index == 0:
            self.head = self.Node(data, self.head)
            return

        current = self.head
        current_index = 0
        while current is not None and current_index < index - 1:
            current = current.next
            current_index += 1

        if current is None:
            raise IndexError("Index exceeds the size of the list")

        current.next = self.Node(data, current.next)

    def append(self, data):
        if self.head is None:
            self.head = self.Node(data)
        else:
            current = self.head
            while current.next is not None:
                current = current.next
            current.next = self.Node(data)

    def find(self, value):
        current = self.head
        while current is not None and current.data != value:
            current = current.next
        return current.data if current else None

    def delete_head(self):
        if self.head is not None:
            self.head = self.head.next

    def delete(self, value):
        if self.head is None:
            return

        if self.head.data == value:
            self.head = self.head.next
            return

        current = self.head
        while current.next is not None and current.next.data != value:
            current = current.next

        if current.next is not None:
            current.next = current.next.next

    def delete_last(self):
        if self.head is None:
            return

        if self.head.next is None:
            self.head = None
            return

        current = self.head
        while current.next.next is not None:
            current = current.next

        current.next = None

    def reverse(self):
        prev = None
        current = self.head
        while current is not None:
            next = current.next
            current.next = prev
            prev = current
            current = next
        self.head = prev

    def traverse(self):
        current = self.head
        while current is not None:
            print(current.data)
            current = current.next

pub struct Node<T> {
    data: T,
    next: Option<Box<Node<T>>>,
}

pub struct LinkedList<T> {
    head: Option<Box<Node<T>>>,
}

impl<T: std::cmp::PartialEq + std::clone::Clone> LinkedList<T> {
    pub fn new() -> Self {
        LinkedList { head: None }
    }

    pub fn prepend(&mut self, data: T) {
        let new_node = Box::new(Node {
            data,
            next: self.head.take(),
        });

        self.head = Some(new_node);
    }

    pub fn insert_before(&mut self, value: T, data: T) {
        let mut current = &mut self.head;
        while current.is_some() && current.as_ref().unwrap().data != value {
            current = &mut current.as_mut().unwrap().next;
        }
        *current = Some(Box::new(Node {
            data,
            next: current.take(),
        }));
    }

    pub fn insert_after(&mut self, value: T, data: T) {
        let mut current = &mut self.head;
        while current.is_some() && current.as_ref().unwrap().data != value {
            current = &mut current.as_mut().unwrap().next;
        }
        let next = current.as_mut().unwrap().next.take();
        current.as_mut().unwrap().next = Some(Box::new(Node {
            data,
            next,
        }));
    }

    pub fn insert_at(&mut self, index: usize, data: T) {
        let mut current = &mut self.head;
        for _ in 0..index {
            current = &mut current.as_mut().unwrap().next;
        }
        *current = Some(Box::new(Node {
            data,
            next: current.take(),
        }));
    }

    pub fn append(&mut self, data: T) {
        let mut current = &mut self.head;
        while current.is_some() {
            current = &mut current.as_mut().unwrap().next;
        }
        *current = Some(Box::new(Node {
            data,
            next: None,
        }));
    }

    pub fn find(&self, value: T) -> Option<T> {
        let mut current = &self.head;
        while current.is_some() && current.as_ref().unwrap().data != value {
            current = &current.as_ref().unwrap().next;
        }
        current.as_ref().map(|node| node.data.clone())
    }

    pub fn delete_head(&mut self) {
        self.head = self.head.take().and_then(|node| node.next);
    }

    pub fn delete(&mut self, value: T) {
        let mut current = &mut self.head;
        while current.is_some() && current.as_ref().unwrap().data != value {
            current = &mut current.as_mut().unwrap().next;
        }
        *current = current.take().and_then(|node| node.next);
    }

    pub fn delete_last(&mut self) {
        let mut current = &mut self.head;
        while current.is_some() && current.as_mut().unwrap().next.is_some() {
            current = &mut current.as_mut().unwrap().next;
        }
        *current = None;
    }

    pub fn reverse(&mut self) {
        let mut prev = None;
        let mut current = self.head.take();
        while let Some(mut node) = current {
            let next = node.next.take();
            node.next = prev;
            prev = Some(node);
            current = next;
        }
        self.head = prev;
    }

    pub fn traverse(&self) {
        let mut current = &self.head;
        while let Some(node) = current {
            println!("{:?}", node.data);
            current = &node.next;
        }
    }
}

class LinkedList<T> {
  class Node<T> {
    constructor(public data: T, public next: Node<T> | null = null) {}
  }

  private head: Node<T> | null = null;

  prepend(data: T) {
    this.head = new Node(data, this.head);
  }

  insertBefore(value: T, data: T) {
    if (this.head === null) {
      return;
    }

    if (this.head.data === value) {
      this.head = new Node(data, this.head);
      return;
    }

    let current = this.head;
    while (current.next !== null && current.next.data !== value) {
      current = current.next;
    }

    if (current.next !== null) {
      current.next = new Node(data, current.next);
    }
  }

  insertAfter(value: T, data: T) {
    let current = this.head;
    while (current !== null && current.data !== value) {
      current = current.next;
    }

    if (current !== null) {
      current.next = new Node(data, current.next);
    }
  }

  insertAt(index: number, data: T) {
    if (index < 0) {
      throw new Error("Index must be greater than or equal to 0");
    }

    if (index === 0) {
      this.head = new Node(data, this.head);
      return;
    }

    let current = this.head;
    let currentIndex = 0;
    while (current !== null && currentIndex < index - 1) {
      current = current.next;
      currentIndex++;
    }

    if (current === null) {
      throw new Error("Index exceeds the size of the list");
    }

    current.next = new Node(data, current.next);
  }

  append(data: T) {
    if (this.head === null) {
      this.head = new Node(data);
    } else {
      let current = this.head;
      while (current.next !== null) {
        current = current.next;
      }
      current.next = new Node(data);
    }
  }

  find(value: T): Node<T> | null {
    let current = this.head;
    while (current !== null && current.data !== value) {
      current = current.next;
    }
    return current;
  }

  deleteHead() {
    if (this.head !== null) {
      this.head = this.head.next;
    }
  }

  delete(value: T) {
    if (this.head === null) {
      return;
    }

    if (this.head.data === value) {
      this.head = this.head.next;
      return;
    }

    let current = this.head;
    while (current.next !== null && current.next.data !== value) {
      current = current.next;
    }

    if (current.next !== null) {
      current.next = current.next.next;
    }
  }

  deleteLast() {
    if (this.head === null) {
      return;
    }

    if (this.head.next === null) {
      this.head = null;
      return;
    }

    let current = this.head;
    while (current.next?.next !== null) {
      current = current.next;
    }

    current.next = null;
  }

  reverse() {
    let prev: Node<T> | null = null;
    let current = this.head;
    let next: Node<T> | null = null;
    while (current !== null) {
      next = current.next;
      current.next = prev;
      prev = current;
      current = next;
    }
    this.head = prev;
  }

  traverse() {
    let current = this.head;
    while (current !== null) {
      console.log(current.data);
      current = current.next;
    }
  }
}