Doubly Linked List

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

Definition

Short

Doubly Linked List is a type of data structure in which each node contains a data part and 2 pointers, one pointing to the next node and another pointing to the previous node in the sequence.

Simplified

Doubly Linked List is like a game of hopscotch. Each square, or "node", holds an item and information about the next and previous squares. You start at the "head" and can move forward or backward to the "tail". You can also add or remove squares during the game.

Detailed

Doubly Linked List in computer science is a sequence of nodes linked in both directions. Each node has two links pointing to its previous and next nodes. The list starts and ends with a terminator, usually a sentinel node or null, aiding in list traversal. If there's only one sentinel node, the list forms a circular link through it. Essentially, it's like having two singly linked lists with the same data but in reverse orders.

Practice

Practice

Aspect	Pseudo Code
Prepend	prepend(value) n = Node(value) if head == ø: head = n tail = n else: n.previous = tail tail.next = n tail = n
Append	append(value): n = Node(value) if head == ø: head = n tail = n else: tail.next = n n.previous = tail tail = n
Search	search(value): current_node = head while current_node != ø and current_node.value != value: current_node = current_node.next return current_node
Delete Head	delete_head(): if head == ø: return ø deleted_head = head if head.next != ø: head = head.next head.previous = ø else: tail = ø head = ø return deleted_head
Delete Node	delete_node(value): current = head while current != ø: if current.value == value: if current == head: head = current.next head.previous = ø else: current.previous.next = current.next current.next.previous = current.previous return current current = current.next
Delete Tail	delete_tail(): if tail == ø: print("The list is empty!") return if head == tail: head = ø tail = ø return prevNode = tail.previous prevNode.next = ø tail = prevNode
Reverse	reverse(): current_node = head previous_node = ø next_node = ø while current_node != ø: next_node = current_node.next previous_node = current_node.previous current_node.next = previous_node current_node.previous = next_node previous_node = current_node current_node = next_node tail = head head = previous_node
Traverse	traversal(): current = head while current != ø: yield current.data current = current.next
Reverse Traversal	reverse_traversal(): current = tail while current != ø: yield current.data current = current.previous

Solution

package main

type Node struct {
	value    interface{}
	next     *Node
	previous *Node
}

type DoublyLinkedList struct {
	head *Node
	tail *Node
}

func (list *DoublyLinkedList) prepend(value interface{}) {
	n := &Node{value: value}
	if list.head == nil {
		list.head = n
		list.tail = n
	} else {
		n.previous = list.tail
		list.tail.next = n
		list.tail = n
	}
}

func (list *DoublyLinkedList) append(value interface{}) {
	n := &Node{value: value}
	if list.head == nil {
		list.head = n
		list.tail = n
	} else {
		list.tail.next = n
		n.previous = list.tail
		list.tail = n
	}
}

func (list *DoublyLinkedList) search(value interface{}) *Node {
	currentNode := list.head
	for currentNode != nil && currentNode.value != value {
		currentNode = currentNode.next
	}
	return currentNode
}

func (list *DoublyLinkedList) deleteHead() *Node {
	if list.head == nil {
		return nil
	}

	deletedHead := list.head

	if list.head.next != nil {
		list.head = list.head.next
		list.head.previous = nil
	} else {
		list.tail = nil
		list.head = nil
	}
	return deletedHead
}

func (list *DoublyLinkedList) deleteNode(value interface{}) {
	current := list.head

	for current != nil {
		if current.value == value {
			if current == list.head {
				list.head = current.next
				list.head.previous = nil
			} else {
				current.previous.next = current.next
				current.next.previous = current.previous
			}
			return
		}
		current = current.next
	}
}

func (list *DoublyLinkedList) deleteLast() {
	if list.tail == nil {
		fmt.Println("The list is empty!")
		return
	}

	if list.head == list.tail {
		list.head = nil
		list.tail = nil
		return
	}

	prevNode := list.tail.previous
	prevNode.next = nil
	list.tail = prevNode
}

func (list *DoublyLinkedList) reverse() {
	currentNode := list.head
	var previousNode *Node
	var nextNode *Node

	for currentNode != nil {
		nextNode = currentNode.next
		previousNode = currentNode.previous

		currentNode.next = previousNode
		currentNode.previous = nextNode

		previousNode = currentNode
		currentNode = nextNode
	}

	list.tail = list.head
	list.head = previousNode
}

func (list *DoublyLinkedList) traversal() {
	current := list.head
	for current != nil {
		fmt.Println(current.value)
		current = current.next
	}
}

func (list *DoublyLinkedList) reverseTraversal() {
	current := list.tail
	for current != nil {
		fmt.Println(current.value)
		current = current.previous
	}
}

public class DoublyLinkedList<T> {

  private Node<T> head = null;
  private Node<T> tail = null;

  public void prepend(T value) {
    Node<T> n = new Node<>(value);
    if (head == null) {
      head = n;
      tail = n;
    } else {
      n.previous = tail;
      tail.next = n;
      tail = n;
    }
  }

  public void append(T value) {
    Node<T> n = new Node<>(value);
    if (head == null) {
      head = n;
      tail = n;
    } else {
      tail.next = n;
      n.previous = tail;
      tail = n;
    }
  }

  public Node<T> search(T value) {
    Node<T> currentNode = head;
    while (currentNode != null && !currentNode.value.equals(value)) {
      currentNode = currentNode.next;
    }
    return currentNode;
  }

  public Node<T> deleteHead() {
    if (head == null) {
      return null;
    }

    Node<T> deletedHead = head;

    if (head.next != null) {
      head = head.next;
      head.previous = null;
    } else {
      tail = null;
      head = null;
    }

    return deletedHead;
  }

  public void deleteNode(T value) {
    Node<T> current = head;

    while (current != null) {
      if (current.value.equals(value)) {
        if (current == head) {
          head = current.next;
          if (head != null) {
            head.previous = null;
          }
        } else {
          current.previous.next = current.next;
          if (current.next != null) {
            current.next.previous = current.previous;
          }
        }
        return;
      }
      current = current.next;
    }
  }

  public void deleteLast() {
    if (tail == null) {
      System.out.println("The list is empty!");
      return;
    }

    if (head == tail) {
      head = null;
      tail = null;
      return;
    }

    Node<T> prevNode = tail.previous;
    if (prevNode != null) {
      prevNode.next = null;
    }
    tail = prevNode;
  }

  public void reverse() {
    Node<T> currentNode = head;
    Node<T> previousNode = null;
    Node<T> nextNode;

    while (currentNode != null) {
      nextNode = currentNode.next;
      previousNode = currentNode.previous;

      currentNode.next = previousNode;
      currentNode.previous = nextNode;

      previousNode = currentNode;
      currentNode = nextNode;
    }

    tail = head;
    head = previousNode;
  }

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

  public void reverseTraversal() {
    Node<T> current = tail;
    while (current != null) {
      System.out.println(current.value);
      current = current.previous;
    }
  }

  public class Node<T> {

    T value;
    Node<T> next = null;
    Node<T> previous = null;

    public Node(T value) {
      this.value = value;
    }
  }
}

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

  Node(value) {
    return { value: value, next: null, previous: null };
  }

  prepend(value) {
    const n = this.Node(value);
    if (this.head === null) {
      this.head = n;
      this.tail = n;
    } else {
      n.previous = this.tail;
      this.tail.next = n;
      this.tail = n;
    }
  }

  append(value) {
    const n = this.Node(value);
    if (this.head === null) {
      this.head = n;
      this.tail = n;
    } else {
      this.tail.next = n;
      n.previous = this.tail;
      this.tail = n;
    }
  }

  search(value) {
    let currentNode = this.head;
    while (currentNode !== null && currentNode.value !== value) {
      currentNode = currentNode.next;
    }
    return currentNode;
  }

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

    const deletedHead = this.head;

    if (this.head.next !== null) {
      this.head = this.head.next;
      this.head.previous = null;
    } else {
      this.tail = null;
      this.head = null;
    }

    return deletedHead;
  }

  deleteNode(value) {
    let current = this.head;

    while (current !== null) {
      if (current.value === value) {
        if (current === this.head) {
          this.head = current.next;
          this.head.previous = null;
        } else {
          current.previous.next = current.next;
          current.next.previous = current.previous;
        }
        return;
      }
      current = current.next;
    }
  }

  deleteLast() {
    if (this.tail === null) {
      console.log("The list is empty!");
      return;
    }

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

    const prevNode = this.tail.previous;
    prevNode.next = null;
    this.tail = prevNode;
  }

  reverse() {
    let currentNode = this.head;
    let previousNode = null;
    let nextNode;

    while (currentNode !== null) {
      nextNode = currentNode.next;
      previousNode = currentNode.previous;

      currentNode.next = previousNode;
      currentNode.previous = nextNode;

      previousNode = currentNode;
      currentNode = nextNode;
    }

    this.tail = this.head;
    this.head = previousNode;
  }

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

  reverseTraversal() {
    let current = this.tail;
    while (current !== null) {
      console.log(current.value);
      current = current.previous;
    }
  }
}

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

    private var head: Node<T>? = null
    private var tail: Node<T>? = null

    fun prepend(value: T) {
        val n = Node(value)
        if (head == null) {
            head = n
            tail = n
        } else {
            n.previous = tail
            tail?.next = n
            tail = n
        }
    }

    fun append(value: T) {
        val n = Node(value)
        if (head == null) {
            head = n
            tail = n
        } else {
            tail?.next = n
            n.previous = tail
            tail = n
        }
    }

    fun search(value: Int): Node? {
        var currentNode = head
        while (currentNode != null && currentNode.value != value) {
            currentNode = currentNode.next
        }
        return currentNode
    }

    fun deleteHead(): Node? {
        if (head == null) {
            return null
        }

        val deletedHead = head

        if (head?.next != null) {
            head = head?.next
            head?.previous = null
        } else {
            tail = null
            head = null
        }

        return deletedHead
    }

    fun deleteNode(value: T) {
        var current = head

        while (current != null) {
            if (current.value == value) {
                if (current == head) {
                    head = current.next
                    head?.previous = null
                } else {
                    current.previous?.next = current.next
                    current.next?.previous = current.previous
                }
                return
            }
            current = current.next
        }
    }

    fun deleteLast() {
        if (tail == null) {
            println("The list is empty!")
            return
        }

        if (head == tail) {
            head = null
            tail = null
            return
        }

        val prevNode = tail?.previous
        prevNode?.next = null
        tail = prevNode
    }

    fun reverse() {
        var currentNode = head
        var previousNode: Node? = null
        var nextNode: Node?

        while (currentNode != null) {
            nextNode = currentNode.next
            previousNode = currentNode.previous

            currentNode.next = previousNode
            currentNode.previous = nextNode

            previousNode = currentNode
            currentNode = nextNode
        }

        tail = head
        head = previousNode
    }

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

    fun reverseTraversal() {
        var current = tail
        while (current != null) {
            println(current.data)
            current = current.prev
        }
    }
}

class Node:
    def __init__(self, value, next=None, previous=None):
        self.value = value
        self.next = next
        self.previous = previous

class DoublyLinkedList:
    def __init__(self):
        self.head = None
        self.tail = None

    def prepend(self, value):
        n = Node(value)
        if self.head is None:
            self.head = n
            self.tail = n
        else:
            n.previous = self.tail
            self.tail.next = n
            self.tail = n

    def append(self, value):
        n = Node(value)
        if self.head is None:
            self.head = n
            self.tail = n
        else:
            self.tail.next = n
            n.previous = self.tail
            self.tail = n

    def search(self, value):
        currentNode = self.head
        while currentNode is not None and currentNode.value != value:
            currentNode = currentNode.next
        return currentNode

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

        deletedHead = self.head

        if self.head.next is not None:
            self.head = self.head.next
            self.head.previous = None
        else:
            self.tail = None
            self.head = None

        return deletedHead

    def deleteNode(self, value):
        current = self.head

        while current is not None:
            if current.value == value:
                if current == self.head:
                    self.head = current.next
                    if self.head is not None:
                        self.head.previous = None
                else:
                    current.previous.next = current.next
                    if current.next is not None:
                        current.next.previous = current.previous
                return
            current = current.next

    def deleteLast(self):
        if self.tail is None:
            print("The list is empty!")
            return

        if self.head == self.tail:
            self.head = None
            self.tail = None
            return

        prevNode = self.tail.previous
        if prevNode is not None:
            prevNode.next = None
        self.tail = prevNode

    def reverse(self):
        currentNode = self.head
        previousNode = None
        nextNode = None

        while currentNode is not None:
            nextNode = currentNode.next
            previousNode = currentNode.previous

            currentNode.next = previousNode
            currentNode.previous = nextNode

            previousNode = currentNode
            currentNode = nextNode

        self.tail = self.head
        self.head = previousNode

    def traversal(self):
        current = self.head
        while current is not None:
            print(current.value)
            current = current.next

    def reverseTraversal(self):
        current = self.tail
        while current is not None:
            print(current.value)
            current = current.previous

pub struct DoublyLinkedList<T> {
    head: Option<Box<Node<T>>>,
    tail: Option<*mut Node<T>>,
}

struct Node<T> {
    value: T,
    next: Option<Box<Node<T>>>,
    prev: Option<*mut Node<T>>,
}

impl<T> DoublyLinkedList<T> {
    pub fn new() -> Self {
        DoublyLinkedList {
            head: None,
            tail: None,
        }
    }

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

        let raw_node = &mut *new_node as *mut Node<T>;

        if let Some(old_head) = self.head.as_mut() {
            old_head.prev = Some(raw_node);
        } else {
            self.tail = Some(raw_node);
        }

        self.head = Some(new_node);
    }

    pub fn append(&mut self, value: T) {
        let mut new_node = Box::new(Node {
            value,
            next: None,
            prev: self.tail,
        });

        let raw_node = &mut *new_node as *mut Node<T>;

        unsafe {
            if let Some(old_tail) = self.tail.as_mut() {
                (*old_tail).next = Some(new_node);
            } else {
                self.head = Some(new_node);
            }
        }

        self.tail = Some(raw_node);
    }

    pub fn search(&self, value: T) -> Option<&Node<T>>
    where
        T: std::cmp::PartialEq,
    {
        let mut current = self.head.as_deref();

        while let Some(node) = current {
            if node.value == value {
                return Some(node);
            }

            current = node.next.as_deref();
        }

        None
    }

    pub fn delete_head(&mut self) -> Option<Box<Node<T>>> {
        self.head.take().map(|mut old_head| {
            self.head = old_head.next.take();

            if let Some(head) = self.head.as_mut() {
                head.prev = None;
            } else {
                self.tail = None;
            }

            old_head
        })
    }

    pub fn delete_node(&mut self, value: T)
    where
        T: std::cmp::PartialEq,
    {
        let mut current = self.head.as_mut();

        while let Some(node) = current {
            if node.value == value {
                let next = node.next.take();

                if let Some(prev) = unsafe { node.prev.as_mut() } {
                    prev.next = next;
                } else {
                    self.head = next;
                }

                return;
            }

            current = node.next.as_mut();
        }
    }

    pub fn delete_last(&mut self) {
        if let Some(tail) = self.tail {
            unsafe {
                if let Some(prev) = (*tail).prev.as_mut() {
                    prev.next = None;
                } else {
                    self.head = None;
                }
            }

            self.tail = None;
        }
    }

    pub fn reverse(&mut self) {
        let mut current = self.head.as_mut();
        let mut prev: Option<*mut Node<T>> = None;

        while let Some(node) = current {
            let next = node.next.take();
            node.prev = next.as_mut().map(|node| &mut **node as *mut Node<T>);
            node.next = unsafe { prev.map(|prev| &mut *prev) };

            prev = Some(node as *mut Node<T>);
            current = next.as_mut();
        }

        std::mem::swap(&mut self.head, &mut self.tail);
    }

    pub fn traversal(&self) {
        let mut current = self.head.as_deref();

        while let Some(node) = current {
            println!("{:?}", node.value);
            current = node.next.as_deref();
        }
    }

    pub fn reverse_traversal(&self) {
        let mut current = self.tail;

        while let Some(node) = unsafe { current.as_ref() } {
            println!("{:?}", node.value);
            current = node.prev;
        }
    }
}

class DoublyLinkedList<T> {
  class Node<T> {
    constructor(public value: T, public next: Node<T> | null = null, public previous: Node<T> | null = null) {}
  }

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

  prepend(value: T) {
    const n = new Node(value);
    if (this.head === null) {
      this.head = n;
      this.tail = n;
    } else {
      n.previous = this.tail;
      if (this.tail) this.tail.next = n;
      this.tail = n;
    }
  }

  append(value: T) {
    const n = new Node(value);
    if (this.head === null) {
      this.head = n;
      this.tail = n;
    } else {
      if (this.tail) this.tail.next = n;
      n.previous = this.tail;
      this.tail = n;
    }
  }

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

  deleteHead(): Node<T> | null {
    if (this.head === null) {
      return null;
    }

    const deletedHead = this.head;

    if (this.head.next !== null) {
      this.head = this.head.next;
      if (this.head) this.head.previous = null;
    } else {
      this.tail = null;
      this.head = null;
    }

    return deletedHead;
  }

  deleteNode(value: T) {
    let current = this.head;

    while (current !== null) {
      if (current.value === value) {
        if (current === this.head) {
          this.head = current.next;
          if (this.head) this.head.previous = null;
        } else {
          if (current.previous) current.previous.next = current.next;
          if (current.next) current.next.previous = current.previous;
        }
        return;
      }
      current = current.next;
    }
  }

  deleteLast() {
    if (this.tail === null) {
      console.log("The list is empty!");
      return;
    }

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

    const prevNode = this.tail.previous;
    if (prevNode) prevNode.next = null;
    this.tail = prevNode;
  }

  reverse() {
    let currentNode = this.head;
    let previousNode: Node<T> | null = null;
    let nextNode: Node<T> | null;

    while (currentNode !== null) {
      nextNode = currentNode.next;
      previousNode = currentNode.previous;

      currentNode.next = previousNode;
      currentNode.previous = nextNode;

      previousNode = currentNode;
      currentNode = nextNode;
    }

    this.tail = this.head;
    this.head = previousNode;
  }

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

  reverseTraversal() {
    let current = this.tail;
    while (current !== null) {
      console.log(current.value);
      current = current.previous;
    }
  }
}