Golang Linked List: Manual and container/list Package Read it later

Linked list, a fundamental data structure in programming, is something that every programmer should have a good grasp of. So, have you ever wondered how to create a linked list in the Go language? If you’re curious to learn the ins and outs of the Golang linked list, you’ve come to the right place. In this blog, we’ll dive deep into the world of linked lists in Go, covering both manual implementation and utilizing the built-in “container/list” package.

What is a Linked List?

A linked list is a collection of nodes connected via links. Each node holds data and a pointer to the next node in the list. Unlike arrays, linked lists have no fixed size and can dynamically adjust as data is added or removed.

This flexibility makes linked lists useful for managing changing data structures efficiently in programming languages like Golang.

Types of Linked Lists

Now that we have a good understanding of what a linked list is, let’s explore the different types of linked lists that exist in the programming world:

1. Singly Linked List: This is the primary type of linked list that consists of nodes containing data and a pointer to the next node. It allows traversal in one direction, from the head to the tail.
2. Doubly Linked List: Besides the next pointer, each node in a doubly linked list has a pointer to the previous node. This allows traversal in both forward and backward directions, enhancing flexibility but requiring more memory.
3. Circular Linked List: The last node in a circular linked list connects back to the first node, forming a loop. This can be useful for scenarios requiring continuous looping or rotation.

Advantages of linked list

Linked lists offer unique advantages that set them apart as a powerful data structure. Understanding these advantages can enhance your programming skills and help you leverage linked lists effectively. Let’s explore these advantages concisely:

1. Dynamic Size: Unlike arrays, linked lists can grow or shrink dynamically, allowing for easy addition or removal of elements without worrying about resizing or reallocation.
2. Efficient Insertion and Deletion: Linked lists excel in insertion and deletion operations, making them ideal for scenarios with large data sets. These operations are faster and more efficient than in arrays due to minimal element shifting.
3. Memory Management: Linked lists allocate memory dynamically, utilizing system resources efficiently. Memory is allocated only when needed, preventing wastage and allowing easy deallocation when nodes are deleted.
4. Implementation of Advanced Operations: Linked lists simplify complex operations like reversing, merging, and splitting data, providing a straightforward and efficient solution compared to other data structures.
5. Versatility in Data Storage: Linked lists can store various data types, including complex structures or other linked lists. This flexibility enables the creation of customized data structures to suit specific application needs.

Use Cases of Golang Linked List

Let’s explore some of the key use cases where linked lists shine:

1. Symbol Table in Compiler Design: In compiler design, symbol tables play a crucial role in storing and managing identifiers, such as variables and functions. Linked lists provide an efficient way to implement symbol tables, allowing for quick insertion, deletion, and lookup operations. This enables efficient compilation and interpretation of programming languages.
2. Undo/Redo Functionality: The undo/redo feature, commonly found in text editors and graphic design software, can be implemented using a linked list. Each action performed by the user is stored as a node in the linked list. The ability to traverse the list backward (undo) and forward (redo) allows users to conveniently revert or reapply changes made to their work.
3. File Systems: Linked lists are widely used in file systems to organize and manage files. Each file is represented as a node in the linked list, with pointers to the next and previous files. This allows efficient traversal and manipulation of files, making tasks like file searching and deletion faster and more manageable.
4. Music and Video Playlists: Have you ever wondered how music or video players maintain playlists? Linked lists provide an excellent solution for this. Each song or video is represented by a node, with pointers to the next and previous tracks. This allows easy navigation through playlists, enabling features like shuffling, repeat modes, and skipping to the next or previous track.
5. Graph Algorithms: Linked lists are frequently used in graph algorithms, where nodes represent vertices and edges. In graph traversal algorithms like Depth-First Search (DFS) and Breadth-First Search (BFS), linked lists facilitate the efficient exploration of adjacent nodes and tracking of visited nodes.

Manually Creating Linked List in Go

Now that we understand the basics of linked lists, let’s dive into the process of creating a linked list in Golang.

Defining Linked List and Node

To create a linked list, we first need to define the LinkedList and Node structs. The LinkedList struct will serve as the container for our nodes, while the Node struct represents each individual node in the linked list.

💡Unaware of Struct in Golang. Learn now before it gets complicated!

type Node struct {
    data interface{}
    next *Node
}

type LinkedList struct {
    head *Node
    tail *Node
}

The Node struct consists of two main parts: the data field to store the actual value of the node, and the next field, which points to the next node in the linked list.

The LinkedList struct, on the other hand, has two pointers:

• head points to the first node, and
• tail points to the last node of the linked list.

💡Pointer plays an important role in LinkedList, so learn about Pointer in Golang.

Add a Node to the Linked List

To add a node to the linked list, we follow these steps:

1. Create a new node with the desired data.
2. Check if the list is empty by verifying if the head is nil.
3. If the list is empty, assign the new node to the head of the list.
4. If the list is not empty, traverse to the last node and update its next pointer to point to the new node.

Here’s an example code example that demonstrates the process of adding a node to the linked list:

func (list *LinkedList) DeleteNode(data int) {
    if list.head == nil {
        return
    }

    if list.head.data == data {
        list.head = list.head.next
        return
    }

    current := list.head
    for current.next != nil {
        if current.next.data == data {
            current.next = current.next.next
            return
        }
        current = current.next
    }
}

Delete a Node from the Linked List

To remove a node from the linked list, we follow these steps:

1. Check if the list is empty by verifying if the head is nil.
2. If the list is empty, no deletion is possible.
3. If the node to be deleted is the head node, update the head to point to the next node in the list.
4. If the node to be deleted is not the head node, traverse the list to find the node, and update the next pointers accordingly.

Here’s an example code snippet that demonstrates the process of deleting a node from the linked list:

func (list *LinkedList) DeleteNode(data int) {
    if list.head == nil {
        return
    }

    if list.head.data == data {
        list.head = list.head.next
        return
    }

    current := list.head
    for current.next != nil {
        if current.next.data == data {
            current.next = current.next.next
            return
        }
        current = current.next
    }
}

Traversing a Linked List

To traverse a linked list, we simply iterate through each node and access its value. We can continue traversing until we reach the end of the list, indicated by a nil next pointer.

Here’s an example that demonstrates how to traverse a linked list and print its values:

func (list *LinkedList) Traverse() {
    currentNode := list.head

    for currentNode != nil {
        fmt.Println(currentNode.data)
        currentNode = currentNode.next
    }
}

Using container/list Package

When it comes to working with linked lists in Golang, we’re in luck! Golang provides a built-in package container/list that takes care of all the heavy lifting for us. This package offers a ready-made implementation of doubly linked lists, making it super convenient and saving us from having to create our own custom solutions.

Before jumping to the usage of container/list package, let’s understand about list in Go.

What is a List in Golang?

In Golang, a list is a linked list data structure consisting of two key components:

1. The Element, and
2. The List.

The Element struct represents an item in the list, holding its value and a reference to the next element.

The List struct serves as the container for the linked list, managing the elements and providing operations to manipulate the list.

Now that we have an idea about List in Golang, let’s dive into the container/list package and discover how it can simplify our linked list adventures in Golang.

Import Container List in Go

When it comes to programming, the import and initialization process plays a crucial role. Let’s begin with the basics and understand how to import the container/list package in Go.

To import container/list, you can simply include the following code in your program:

import "container/list"

By adding this line, you inform the Go compiler that you want to import the list package from the container library. This enables you to utilize the functions provided by the package.

Now that we have successfully imported the necessary package, let’s move on to initializing a list in Go.

Initializing a list in Go

Initialization is a crucial step before we can start working with a list effectively. Let’s explore how to do it.

To initialize an empty list in Go, you can use the list.New() function provided by the container/list package. This function creates a new list with its head and tail pointers set to nil, indicating that the list currently contains no elements.

Here’s an example code example that demonstrates the initialization process:

l := list.New()    // Initialize an empty list

In the above example, we use the list.New() function to create a new list and assign it to the variable l. This sets up the initial structure of the list, allowing us to perform various operations on it.

To verify that the list has been initialized successfully, we can print its contents using the fmt.Println() function:

fmt.Println(l)

When executed, the code above will display the following output:

&{{0x25ac31 0x25ac31 <nil> <nil>} 0}

The output showcases the list’s internal structure, including its head and tail pointers (both pointing to the same memory location). At this point, the list is empty, as indicated by the <nil> values for both the head and tail.

Adding items to the list

Now that we have our list initialized in Go, it’s time to fill it with some awesome data! Adding items to the list is a crucial operation, and we’ve got you covered with two ways to do it: adding items to the front and adding items to the back.

Let’s dive into each method and learn how it’s done.

Adding Items to the Front

To add an item to the front of the list, we can use the PushFront function. It’s as simple as passing the item you want to add as the parameter.

For example:

l.PushFront(10)

This will add the value 10 to the front of the list. Easy, right?

But wait, there’s more! Did you know that you can even push an entire list to the front of another list? It’s mind-blowing! This can be achieved using the PushFrontList function.

Here’s an example to demonstrate how it works:

l.PushFrontList(l2)

By executing this code, the entire l2 list will be inserted at the front of the l list. It’s a powerful feature that can come in handy in certain scenarios.

📝Note: Make sure that the list you want to insert is properly initialized.

Adding Items to the Back

Now, let’s move on to adding items to the back of the list. You guys are smart, so you’ve probably already guessed the function to use. That’s right! Replace the word “Front” with “Back” and you’re good to go.

To add an item to the back of the list, we can use the PushBack function. It works similarly to PushFront, but instead of adding the item to the front, it adds it to the back.

Here’s an example:

l.PushBack(10)

This code example will add the value 10 to the back of the list.

But wait, there’s more to discover! You can also add an entire list to the back of another list using the PushBackList function. It follows the same principle as PushFrontList, but adds the list to the back instead. Take a look at this example:

l.PushBackList(l2)

Executing this code will append the entire l2 list to the back of the l list.

Peek the List

Alright, let’s dive into a useful operation called “Peeking“. So, imagine you’ve added several items to your list, both at the front and back. Now, if we ask you to show us the first and last element, can you do it? Of course, you can! Thankfully, Golang’s container/list comes to the rescue with its handy Front and Back methods.

To access the first element in the list, we can simply use the Front method. And to retrieve the last element, we can rely on the Back method. Let’s take a look at an example:

fmt.Println(l.Front())
fmt.Println(l.Back())

By calling l.Front(), we can display the value of the first element in the list. Similarly, using l.Back(), we can retrieve the value of the last element. These methods allow us to peek at the list and quickly access the desired elements.

📝 Note: The Front and Back methods return the element’s value, not the element itself. So, we can easily print or process the values returned by these methods.

Length of the List

Now that we have added multiple items and lists in the previous section, you might be curious to know just how big our list has become. Luckily, Golang provides a convenient method called Len() that allows us to find out the length of a linked list effortlessly.

To retrieve the length of a linked list, we can utilize the Len() method as shown below:

fmt.Println(l.Len())

This simple line of code will output the length of our linked list. It’s as easy as that!

Remove Items from the List

When it comes to managing our list, there might be times when we need to remove specific items from it. It can be a daunting task, especially if our list is lengthy. But fear not! Golang’s container/list package comes to the rescue with its Remove() method. This method allows us to easily remove items from our list, making our lives much easier.

To remove an item from our list, we simply call the Remove() method and pass in the value we want to remove as an argument.

Let’s take a look at the code example below:

l.Remove(v)

Here, l represents our list, and v is the value we want to remove. By calling this method, Golang will swiftly eliminate the specified item from the list, keeping everything neat and tidy.

📝 Note: Make sure that the value passed as an argument in the Remove() method matches exactly with the item we want to remove. If there are multiple occurrences of the same value in the list, only the first occurrence will be removed.

Traversing the List

Now that we have our list up and running, it’s time to embark on a traversing adventure and explore each element within the list. Traversing a linked list allows us to access and examine each item individually. Let’s dive right in!

To traverse our linked list in Golang, we can utilize a for loop that starts at the first node and iterates until we reach the end. Here’s an example of how we can achieve this:

for e := l.Front(); e != nil; e = e.Next() {
    fmt.Println(e)
}

In this example, we initialize a variable e with the value of the first node (l.Front()). The loop condition e != nil ensures that we continue traversing until we reach the end of the list (where e becomes nil). Inside the loop, we print the current element e using fmt.Println().

Wrapping Up

In conclusion, we have explored the world of Golang linked lists, covering the fundamentals, implementation techniques, advanced operations, and important considerations. By understanding the basics and mastering the essential operations, you now have the skills to efficiently store and manipulate data using linked lists in Golang.

Remember to continue practicing, applying your knowledge to real-world scenarios, and embracing new challenges. We’re here to support you on your coding journey. Happy coding!

Frequently Asked Questions (FAQs)

Reference

• https://golang.org/pkg/container/list/
• https://en.wikipedia.org/wiki/Linked_list