§ Singly Linked List

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

Time Complexity

Access

We have no given info to determine where 3rd element is in the given list. The only way to find the 3rd element is by traversing the node one by one from the head. Therefore, the time complexity for the access operation is going to be O(n).

The exception would be accessing the head and the tail, or the first and the last element, which is going to be O(1).The first element will always be head.data if exists, and the tail will be tail.data. If tail is not implemented, then, it will also be O(n).

Search

Since we need to check every node in the list, the time complexity is going to be O(n).

Insert

There are three different scenarios when inserting to a linked list: 1) at the head, 2) at the tail, and 3) in between nodes.

1. Inserting at the head can be done in constant time: new_Node.next = head.

2. Inserting at the tail can be vary. If tail is given, it will be constant: tail.next = new_Node. Otherwise, it will be O(n) because you need to traverse the list all the way up to the last node.

3. In order to insert a node in between the node, you first need to locate the position of the node to insert. This requires O(n) in average. Thus, the time complexity becomes linear for inserting a new node in between the nodes.

Delete

Similar to the insert, deletion also has couple scenarios to consider: 1) deleting the head, 2) deleting the tail, and 3) deleting the middle

1. Straightforward. it’s constant: head = head.next

2. Unlike insertion, whether you have tail or not, the time complexity will be O(n). Because in order to delete tail, we need tail.prev which singly linked list doesn’t have. This means you need to traverse the list from the head.

3. Same as insertion. Since you need to locate the position to delete a node, it costs linear time in average, O(n).

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

	def each
		curr = @head

		while curr
			yield curr
			curr = curr.next
		end
	end
end