§ Doubly Linked List

by Jii
…
note
|
diary

Time Complexity

Access

Since there’s no way to directly access the nth node, we need to traverse the list from the head. This causes the access operation to be linear, which is O(n).

The exception would be accessing the first and the last node. Since first node will always be head, it will be constant, O(1). Same with the last node which is tail.

We need to compare each node one at a time to find the target value. This is linear, O(n).

Insert

Inserting at the head is constant because we have a head node.

Inserting a node in between node is linear because we need to locate the position by traversing the list.

About inserting node at the end, unlike Singly Linked List which took linear time, doubly linked list can perform the action at constant time, O(1) if we have tail. This is because we can access the previous node using tail.prev.

Delete

The time complexity for the deletion is similar to the insertion.

Deleting node at the head and tail both can be done at constant time because of the prev point. But for nodes in between, we still need to locate the position which causes linear time in average.

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
Backlinks: