Linked list is one of the most common data structures. An interesting definition of linked list is from Algorithms book by Robert Sedgewick which said:

A linked list is a recursive data structure that is either empty (null) or a reference to a node having a generic item and a reference to a linked list.

Let's think of a linked list as a chain of recursive nodes. It is recursive because it might consist of a node, that stores a reference to another node. If it doesn't, then it might be the last or the only node in the linked list.

A node can be represented as a type of struct

type Node struct {
  Value int
  Next *Node
}

and so is our linked list that has head, tail, and length property.

type LinkedList struct {
  Head *Node
  Tail *Node
  Length int
}

Please be aware that both head and tail are stored as a pointer.

Our linked list will implement several methods such as:

• IsEmpty() -> bool
• AddLast(item)
• AddFirst(item)
• RemoveLast()
• RemoveFirst()

The first method IsEmpty checks whether the head of a linked list contains a node. This method will be helpful for other following methods.

func (l LinkedList) IsEmpty() bool {
  if l.Head == nil {
    return true
  }
  return false
}

AddLast and AddFirst take in a node and puts it at the end and front of the linked list respectively. We also need to check if the linked list is empty because if it is, both head and tail point to the same node. In the end, the length must be incremented. These two methods take time complexity of O(1).

func (l *LinkedList) AddFirst(node *Node) {
  if l.IsEmpty() {
    l.Head = node
    l.Tail = node
  } else {
    node.Next = l.Head
    l.Head = node
  }
  l.Length++
}

func (l *LinkedList) AddLast(node *Node) {
  if l.IsEmpty() {
    l.Head = node
    l.Tail = node
  } else {
    l.Tail.Next = node
    l.Tail = node
  }
  l.Length++
}

Removing the last node requires us to traverse through the linked list until right before the tail so that we can remove its reference to the current tail. The traversal makes this operation takes linear or O(n) time. Don't forget to decrement the length for each removal.

func (l *LinkedList) RemoveLast() {
  if l.IsEmpty() {
    return
  }

  current := l.Head
  for current.Next.Next != nil {
    current = current.Next
  }

  current.Next = nil
  l.Tail = current
  l.Length--
}

On the other end, removing the head is pretty straightforward. We only need to replace the current head with the reference of its next node. This operation takes O(1) time.

func (l *LinkedList) RemoveFirst() {
  if l.IsEmpty() {
    return
  }

  l.Head = l.Head.Next
  l.Length--
}

To see our linked list in action, I create a function to print the list

func PrintList(l LinkedList) {
  list := ""
  for l.Head.Next != nil {
    list += strconv.Itoa(l.Head.Value) + " - "
    l.Head = l.Head.Next
  }
  list += strconv.Itoa(l.Head.Value)
  fmt.Println(list)
}

Finally, let's put all things together.

func main() {
  myLinkedList := LinkedList{}
  fmt.Println(myLinkedList.IsEmpty()) // true

  node1 := &Node{Value: 33}
  node2 := &Node{Value: 44}
  node3 := &Node{Value: 55}
  node4 := &Node{Value: 66}

  myLinkedList.AddLast(node1) // [33]
  myLinkedList.AddLast(node2) // [33, 44]
  myLinkedList.AddFirst(node3) // [55, 33, 44]
  myLinkedList.AddFirst(node4) // [66, 55, 33, 44]
  PrintList(myLinkedList)

  fmt.Println(myLinkedList.Head.Value)  // 66
  fmt.Println(myLinkedList.Tail.Value) // 44
  fmt.Println(myLinkedList.Length) // 4

  myLinkedList.RemoveLast() 
  PrintList(myLinkedList) // [66, 55, 33]

  myLinkedList.RemoveFirst()
  PrintList(myLinkedList) // [55, 33]
  fmt.Println(myLinkedList.Length) // 2
}

Hope you learn something like I did. Thank you!