Doubly Linked List is a two-way traffic

Doubly linked list is a linked list allowing data to be accessed and traversed in both forward and backward directions. This is because every node in a doubly linked list not only contains the next pointer, but also a pointer to the previous node.

struct Node {
    T data;
    Node *next;
    Node *prev;
}

Time Complexity

• Access
  • O(n) where n is number of nodes.
    • We have to traverse from the head and compare each node to find the target node.
  • Ω(1) for accessing the head and the tail (if tail node exists)
• Search
  • O(n) where n is number of nodes.
    • Unlike an array, random access is not possible.
• Insert
  • O(n) where n is number of nodes.
    • We need to locate the correct position by traversing a node one by one which takes linear time. Linking a node itself is constant.
  • Ω(1) for inserting at the head and tail (if tail node exists).
• Delete
  • O(n) where n is number of nodes.
    • We need to locate a node before the target we’re going to remove, so that we can un-link a pointer.
  • Ω(1) for removing the head and tail (if tail node exists).
    • Unlike singly linked list where deleting a tail is O(n), doubly linked list can do it in constant time because of the ability to traverse backward.

Implementation

class Node
  attr_accessor :prev, :next
  attr_reader :data

  def initialize(data, _prev=nil, _next=nil)
      @data = data
      @prev = _prev
      @next = _next
  end
end

class DoublyLinkedList
  attr_accessor :head, :tail

  def initialize
      @head = @tail = nil
      @size = 0
  end

  def push_front(data)
      new_node = Node.new(data)

      if @head == nil
          @head = @tail = new_node
      else
          new_node.next = @head
          @head.prev = new_node
          @head = new_node
      end

      @size += 1
  end

  def push_back(data)
      new_node = Node.new(data)

      if @tail == nil
          @head = @tail = new_node
      else
          @tail.next = new_node
          new_node.prev = @tail
          @tail = new_node
      end

      @size += 1
  end

  def insert_at(data, pos)
      raise "err: invalid position." if pos < 0 || pos >= @size

      curr = @head

      pos.times { curr = curr.next }

      new_node = Node.new(data)
      new_node.next = curr
      new_node.prev = curr.prev
      curr.prev.next = new_node
      curr.prev = new_node

      @size += 1
  end

  def pop_front
      raise "err: list is empty" if @head == nil

      @head = @head.next
      @head.prev = nil

      @size -= 1
  end
  
  def pop_back
      raise "err: list is empty" if @tail == nil

      @tail = @tail.prev
      @tail.next = nil

      @size -= 1
  end

  def delete_at(pos)
      raise "err: invalid position" if pos < 0 || pos >= @size

      curr = @head

      if pos == 0
          pop_front
      elsif pos == @size - 1
          pop_back
      else
          pos.times { curr = curr.next }

          curr.prev.next = curr.next
          curr.next.prev = curr.prev

          @size -= 1
      end

      
  end

  def first
      @head
  end

  def last
      @tail
  end

  def size
      @size
  end

  def each
      curr = @head

      while curr
          yield curr
          curr = curr.next
      end
  end

  def to_s
      each { |node| print "#{node.data} "}
      puts "   (#{@size})"
  end
end