Introduction

What are data structures after all? Data structures are organized ways to store, manage and arrange data so it can be used efficiently in different computations. They define the format and relationships among data elements, enabling better data retrieval, manipulation and storage. There are several types of data structures and today we will talk about Lists and some variations like Array Lists, Singly Linked Lists and Doubly Linked Lists.

Let's start by defining a Container interface that can generalize data structures. This interface will have the following methods:

type Container interface {
  Empty() bool
  Size() int
  Clear()
  Values() []interface{}
  String() string
}

All list implementations in this article will follow this interface.

Helper Functions

Data structures can be ordered or unordered. In this article, all ordered data structures will provide stateful iterators and some of them will also allow enumerable functions.

An iterator is an interface used to iterate through the data structure. In the implementations of this article, the iterator of data structures that provide one can be obtained using the Iterator() method. Once obtained, the iterator.Next() function can be used to move the iterator cursor to the next element in the data structure, this function returns true if there is a next element. Once Next() is called, the current element that the cursor points to can be obtained through the Value() function.

The basic Iterator interface looks like this:

type Iterator[V any] interface {
  Next() bool
  Value() V
  Begin() // This function resets the iterator to a one-before-first state, so that when you call Next(), it doesn't go to the second element.
  First() bool // Moves the cursor to the first element of the iterator
}

This iterator has a stateful implementation, so the Next(), Begin() and First() functions all change the state of the iterator by moving its cursor.

Lists

There are a few types of Lists. Some of them are Array Lists, Singly Linked Lists, Doubly Linked Lists and Multi-Linked Lists. Each one of those can have variations and unique applications that we will exemplify here. A List is basically a linear collection of elements where each element is stored in sequence and can be accessed individually. Lists allow dynamic insertion, deletion and traversal of elements, making them flexible for organizing data. Depending on the implementation, lists can support random access or require sequential traversal.

Array Lists

An Array List is a list backed by a dynamic array that grows and shrinks implicitly. Its data is stored in a contiguous block of memory and this list allows random access, you can access any element at any time, which makes lookup very fast (O(1) complexity). On the other hand, insertion can be expensive since it may require shifting elements (especially when inserting in the middle). If the internal array reaches its capacity, a new and larger array is allocated and existing elements are copied into it.

In practice, this is a good default list implementation when reads and indexed access happen frequently.

A basic ArrayList implementation following the Container interface:

type ArrayList struct {
  elements []interface{}
}

func NewArrayList(values ...interface{}) *ArrayList {
  return &ArrayList{elements: append([]interface{}{}, values...)}
}

func (l *ArrayList) Empty() bool {
  return len(l.elements) == 0
}

func (l *ArrayList) Size() int {
  return len(l.elements)
}

func (l *ArrayList) Clear() {
  l.elements = nil
}

func (l *ArrayList) Values() []interface{} {
  return append([]interface{}{}, l.elements...)
}

func (l *ArrayList) String() string {
  return fmt.Sprintf("%v", l.elements)
}

Singly Linked Lists

Singly Linked Lists are a type of List where each element stores a reference only to the next element. There is only one reference per node and it always points forward in the sequence.

This makes insertion and deletion at the head very efficient (O(1)), because we only need to update one pointer. However, access by index is sequential (O(n)), because to reach an element we need to traverse nodes from the start until we find the desired position.

A basic node model for a singly linked list in Go looks like this:

type SinglyNode[V any] struct {
  Value V
  Next  *SinglyNode[V]
}

Singly linked lists are useful when your access pattern is mostly sequential and when cheap insertions/removals at the beginning are more important than random access.

A basic SinglyLinkedList implementation following the same interface:

type SinglyLinkedList struct {
  head *SinglyNode[interface{}]
  size int
}

func (l *SinglyLinkedList) Empty() bool {
  return l.size == 0
}

func (l *SinglyLinkedList) Size() int {
  return l.size
}

func (l *SinglyLinkedList) Clear() {
  l.head = nil
  l.size = 0
}

func (l *SinglyLinkedList) Values() []interface{} {
  values := make([]interface{}, 0, l.size)
  for n := l.head; n != nil; n = n.Next {
    values = append(values, n.Value)
  }
  return values
}

func (l *SinglyLinkedList) String() string {
  return fmt.Sprintf("%v", l.Values())
}

Doubly Linked Lists

Doubly Linked Lists are similar to singly linked lists, but each element stores two references: one to the next element and one to the previous element.

Because of that, traversal can happen in both directions and removals become easier when you already hold a reference to the current node, since you can reconnect previous and next nodes directly.

A basic node model for a doubly linked list in Go is:

type DoublyNode[V any] struct {
  Value V
  Prev  *DoublyNode[V]
  Next  *DoublyNode[V]
}

This extra flexibility comes with an extra memory cost, because every node stores one more pointer.

A basic DoublyLinkedList implementation:

type DoublyLinkedList struct {
  head *DoublyNode[interface{}]
  tail *DoublyNode[interface{}]
  size int
}

func (l *DoublyLinkedList) Empty() bool {
  return l.size == 0
}

func (l *DoublyLinkedList) Size() int {
  return l.size
}

func (l *DoublyLinkedList) Clear() {
  l.head = nil
  l.tail = nil
  l.size = 0
}

func (l *DoublyLinkedList) Values() []interface{} {
  values := make([]interface{}, 0, l.size)
  for n := l.head; n != nil; n = n.Next {
    values = append(values, n.Value)
  }
  return values
}

func (l *DoublyLinkedList) String() string {
  return fmt.Sprintf("%v", l.Values())
}

Which one should you use?

There is no universal best list implementation, the best choice depends on your use case:

• Array List: Better when you need frequent reads by index.
• Singly Linked List: Better when you mostly traverse forward and do frequent insertions/removals at the head.
• Doubly Linked List: Better when you need two-way traversal or frequent removals in the middle when node references are available.

Understanding those trade-offs is more important than memorizing definitions.

Conclusion

Today we covered the list topic end-to-end: what lists are, the differences between Array Lists, Singly Linked Lists and Doubly Linked Lists, and practical examples for each implementation.

In the next article we will move to another data structure category and keep using the same Container and iterator approach shown here.