Singly Linked List is a one-way traffic
by Jii
…
note
|
diary

Singly Linked List is a type of a linked list where each node contains a data and a pointer to reference the next node.

struct Node {
    T data;
    Node *next;
}

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.
      • A random access is not possible in a linked list.
  • 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.

Implementation

Node = Struct.new(:data, :next) do
    def new
        @data = self.data
        @next = self.next
    end
end
    
class SinglyLinkedList
    def initialize()
        @head = nil
        @size = 0
    end
    
    def push_front(data)
        if @head == nil
            @head = Node.new(data, nil)
        else
            @head = Node.new(data, @head)
        end
    
        @size += 1
    end
    
    def push_back(data)
        new_node = Node.new(data, nil)
    
        if @head == nil
            @head = new_node
        else
            temp = @head
            while temp.next
                temp = temp.next
            end
    
            temp.next = new_node
        end
    
        @size += 1
    end
    
    def pop_front
        raise "err: list is empty" if @head == nil
        
        @size -= 1
        @head = @head.next
    end
    
    def pop_back
        raise "err: list is empty" if @head == nil
    
        curr = @head
        if curr.next == nil
            @head = nil
        else
            while curr.next && curr.next.next != nil
                curr = curr.next
            end
    
            curr.next = nil
        end
    
        @size -= 1
    end
    
    def del_at(pos)
        raise "err: invalid 'pos' was given" if pos < 0 || pos >= @size
    
        if pos == 0
            pop_front
        elsif pos == @size-1
            pop_back
        else
            curr = @head
            (pos-1).times { curr = curr.next }
            curr.next = curr.next.next
            @size -= 1
        end
    
    end
    
    def del(data)
        pos = find(data)
        return -1 if pos == -1
    
        del_at(pos)
    end
    
    def find(data)
        return -1 if @head == nil
    
        curr = @head
        pos = 0
        while curr 
            return pos if curr.data == data
            curr = curr.next
            pos += 1
        end
    
        -1
    end
    
    def size
        return @size    
    end
    
    def reverse
        c = @head
        n = @head
        p = nil
    
        while n
            n = c.next 
            c.next = p
            p = c
            c = n
        end
    
        @head = p
    end
    
    def print(delim=' ')
        return if @head == nil
    
        temp = @head
    
        while temp.next != nil
            printf("%d%c ", temp.data, delim)
            temp = temp.next
        end
    
        printf("%d\n", temp.data)
    end
    
    def clear
        @head = nil
        @size = 0
    end
end
Backlinks: