Implementing a Singly Linked List in Go

💡 Linked List

• A linked list stores elements in a node. The node consists of two parts, i.e., data and the address to the next node in sequence.

• Linked lists are used when you want to add or remove elements from the list without worrying about the size of the list. They are often used to implement other data structures like stacks, queues, and even hash tables. In computer science, they can be used to represent sequences or lists of items.

👨‍🏫 Refer my previous post about Data structures, if you are new to Data structures.

Overview

LINKED LIST
- 💡 contains: NODE (value, next)
- 📦 items: LIST (head, tail, len)
- 🚦 methods: ADD (T), REMOVE (T), LENGHT, TRAVERSE -> add to tail
- ⚡️ extra: , ADD-HEAD, POP-HEAD, POP-TAIL, REVERSE

---

⭐️ In here, we use Go Generics and comparable data type. You don’t need to have a prior knowledge of Go Generics syntaxes as this is a good example of usage of Generics and a good opportunity to get familiarize with Go Generics syntaxes.

Let’s get started.

Implementation

Node and Linked list

type Node[T comparable] struct {
    value T
    next  *Node[T]
}

type LinkedList[T comparable] struct {
    head *Node[T]
    tail *Node[T]
    len  int
}

Factory

func New[T comparable]() *LinkedList[T] {
    return &LinkedList[T]{}
}

Add

func (ll *LinkedList[T]) Add(v T) {
    newNode := &Node[T]{value: v}

    if ll.len == 0 {
       ll.head = newNode
    } else {
       ll.tail.next = newNode
    }

    ll.tail = newNode
    ll.len++
}

Remove

func (ll *LinkedList[T]) Remove(v T) error {
    if ll.len == 0 {
       return ErrEmptyList
    }

    if ll.head.value == v {
       ll.head = ll.head.next
       if ll.head == nil {
          ll.tail = nil
       }

       ll.len--
       return nil
    }

    current := ll.head
    for current.next != nil {
       if current.next.value == v {
          current.next = current.next.next
          if current.next == nil {
             ll.tail = current
          }

          ll.len--
          return nil
       }

       current = current.next
    }

    return ErrItemNotFound
}

var (
	ErrEmptyList    = errors.New("empty list")
	ErrItemNotFound = errors.New("item not found")
)

Length and Traverse

func (ll *LinkedList[T]) Length() int {
    return ll.len
}

func (ll *LinkedList[T]) String() string {
    if ll.len == 0 {
       return ""
    }

    var builder strings.Builder
    current := ll.head
    for current != nil {
       builder.WriteString(fmt.Sprintf("%v ", current.value))
       current = current.next
    }

    return builder.String()
}

---

⚡️ Let’s see how to implement extra functionalities which are not directly related to generic linked list implementation.

Add Head

func (ll *LinkedList[T]) AddHead(v T) {
    newNode := &Node[T]{value: v, next: ll.head}

    if ll.len == 0 {
       ll.tail = newNode
    }

    ll.head = newNode
    ll.len++
}

Pop Head

func (ll *LinkedList[T]) PopHead() (T, error) {
    var zeroV T

    if ll.len == 0 {
       return zeroV, ErrEmptyList
    }

    v := ll.head.value
    ll.head = ll.head.next
    if ll.head == nil {
       ll.tail = nil
    }
    ll.len--

    return v, nil
}

// var ErrEmptyList    = errors.New("empty list")

Pop Tail

func (ll *LinkedList[T]) PopTail() (T, error) {
    var zeroV T

    if ll.len == 0 {
       return zeroV, ErrEmptyList
    }

    if ll.len == 1 {
       v := ll.head.value
       ll.head, ll.tail, ll.len = nil, nil, 0
       return v, nil
    }

    current := ll.head
    for current.next != ll.tail {
       current = current.next
    }

    v := ll.tail.value
    current.next = nil
    ll.tail = current
    ll.len--

    return v, nil
}

// var ErrEmptyList    = errors.New("empty list")

Reverse

func (ll *LinkedList[T]) Reverse() {
    if ll.len < 2 {
       return
    }

    var x, y, current *Node[T]
    current, ll.tail = ll.head, ll.head

    for current != nil {
       y = current.next
       current.next = x
       x = current
       current = y
    }

    ll.head = x
}

---

⭐️ To practice further, add following new methods to the linked list

• HEAD : to get the value of the first element

• HAS : to verify the value already exists in the list

• ADD TO INDEX: to add the value to a particular index of the list

• REMOVE INDEX: to remove the value of a particular index of the list

---