How to Create Linked Lists in Go

If you're looking to learn about data structures in Go, linked lists are a great place to start. They're a fundamental concept that offers a practical way to understand how data can be structured and manipulated. In this blog post, we're going to explore how to implement and manipulate linked lists in Go.

Introduction to Linked Lists

A linked list is a linear data structure where each element is a separate object that contains a pointer or a reference to the next object in line. Each element, also known as a node, contains two items: the data and a reference to the next node. The last node points to a null value indicating the end of the chain.

Defining a Node in Go

In Go, we can define the Node struct as follows:

type Node struct {
    data int
    next *Node
}

Here, the data attribute will hold the integer value of the node. The next attribute, on the other hand, is a pointer to another node, denoting the link to the next node.

Defining a Linked List in Go

The next step is to define our linked list. A linked list is a chain of nodes, so we need only to keep track of the first node in this chain, also known as the head node.

type LinkedList struct {
    head *Node
    length int
}

In this struct, head is a pointer to the first node in the linked list and length will keep track of the length of the list.

Adding Elements to the List

We can add elements to our list by creating new nodes and having them point to the existing head of the list, thereby placing our new node at the start of the list.

func (l *LinkedList) Prepend(n *Node) {
    second := l.head
    l.head = n
    l.head.next = second
    l.length++
}

Iterating Over a Linked List

We can print out all the elements of our linked list by iterating over it. Starting from the head, we continue to the next node, until we reach a node that points to null.

func (l *LinkedList) PrintAllNodes() {
    toPrint := l.head
    for l.length != 0 {
        fmt.Println(toPrint.data)
        toPrint = toPrint.next
        l.length--
    }
}

Deleting an Element from the List

Finally, let's look at how we can delete a node from our list. We'll do this by updating the next attribute of the node preceding the one we want to delete, making it point to the node following the one we're deleting.

func (l *LinkedList) DeleteWithValue(value int) {
    if l.length == 0 {
        return
    }
    if l.head.data == value {
        l.head = l.head.next
        l.length--
        return
    }
    toDelete := l.head
    for toDelete.next.data != value {
        if toDelete.next.next == nil {
            return
        }
        toDelete = toDelete.next
    }
    toDelete.next = toDelete.next.next
    l.length--
}

That's a quick introduction on how to implement and work with linked lists in Go! With this knowledge, you can now create, add, iterate over, and delete elements from a linked list in Go. Remember that understanding and implementing data structures is a crucial part of becoming a proficient Go programmer, so keep practicing and exploring!