This repository has implementations of data structures in Go. They are purely for my own learning, do not use these in real software.
A linked list is data structure that stores data as a set of nodes.
Each node contains a link to the node after it, called next
, until a nil
next
node signifies the end of the list.
The linked list in this package can only hold strings.
Linked lists allow the following operations:
-
Append
Append
adds an node to the end of the Linked List. It is aO(n)
operation, since the list has to be fully traversed to add a new node at the end. -
Prepend
Prepend
adds a node to the beginning of the linked list. It runs inO(1)
time, since it simply modifies thenext
pointer at the head of the list. -
Contains
Contains
returnstrue
if a Linked List contains a particular value, orfalse
if it doesn't. SinceContains
requires traversing the list, it is aO(n)
operation. -
Delete
Delete
removes a node from a list by adjusting thenext
pointer of the node before it. This is aO(n)
operation, since the list has to be traversed to find the target. -
Traverse
Traverse
returns the values in a Linked List as a[]string
slice.Traverse
is done inO(n)
time, as every node in the list must be visited.