Linked lists offer an alternative to array-based sequences i.e Lists. Both array-based sequences and linked lists keep elements in a specific order, but the implementation of this feature varies widely between the two.

Arrays offer a more centralized representation with one large chunk of memory capable of accommodating references to many elements. A linked list on the other hand relies on a more distributed architecture in which a lightweight object known as a node is used to represent each individual element of the linked list.

Each node in a linked list maintains a reference to its constituent elements and one or more references to neighboring nodes depending on whether it’s a single-linked list implementation or a doubly-linked list implementation. This representation then allows us to collectively represent the linear order of our sequence.

SINGLY-LINKED LISTS

Below we are going to give implementations of the singly-linked list in both Python and Golang as Queue, now this can be extended to Stacks and also trees for doubly-linked lists.

Memory use

Compared to a doubly-linked list, a single list occupies less memory because it needs only one pointer to its successor. Each pointer variable holds the address to an element, and the pointer occupies 4 bytes; therefore the memory space occupied by the pointer variable in the singly linked list is 4 bytes. So memory also expands as per O(n) with n representing the number of elements and the 4 bytes being held constant for each pointer.

Time complexity

A singly linked list has an access time of 0(1), and a search time of O(n), since we have to traverse the whole list from first to last in one direction, it has an insertion time of O(n) and deletion time of O(n), in the worst case and average case time.

Golang Singly-linked list Queue Implementation