Implementing Linked Lists in Go

Introduction to Linked Lists

Hello there! Today, we will explore linked lists, a core data structure crucial for organized data management and establishing relationships between data. We will mark some essential milestones: an introduction to linked lists, their real-world applications, their implementation in Go, and the different operations you can perform on them. By the end of this lesson, you will be well-equipped to implement and operate linked lists using Go. Let's get started!

Understanding the Concept

A linked list is a linear data structure similar to arrays. However, unlike arrays, they are not stored in contiguous memory locations. Each element in a linked list is part of a node . A node comprises data and a reference (or link) to the next node in the sequence. This structure facilitates efficient insertions and deletions. The head is also an essential concept in linked lists . It is the first node in the list and serves as a reference to the entire list. The head is not set if the linked list is empty. Linked lists come up quite often in coding challenges. There are two popular types of linked lists : singly linked lists and doubly linked lists . While singly linked lists might not be extensively used in real-world applications, they form the foundational knowledge for understanding doubly linked lists, which are indeed quite common. A singly linked list contains nodes with a single link pointing to the next node, whereas a doubly linked list has nodes with links to both the next and the previous nodes.

Implementing Linked Lists - Creating Node

To begin implementing linked lists, we first need to understand the structure of a node, the building block of a linked list . In Go, we'll define a struct to serve as a blueprint for a node . A Node struct mainly consists of a data (the data you want to store) field and a next field (the reference to the next node). In our case, we'll create a Node struct to store integer data, with a constructor-like function to initialize the node. Go package main type Node struct {Data int Next *Node} func NewNode(data int) *Node {return &Node{Data: data, Next: nil}} package main type Node struct {Data int Next *Node} func NewNode(data int) *Node {return &Node{Data: data, Next: nil}} In Go, the Next field of the Node struct is of type *Node, which is a pointer to another Node . Pointers allow us to create references to other nodes, enabling the dynamic linking that forms the basis of linked lists. Without this, nodes would be isolated entities without connections to subsequent elements in the list. Fantastic! You now know how to create a Node in a linked list .

Join the 1M+ learners on CodeSignal

Be a part of our community of 1M+ users who develop and demonstrate their skills on CodeSignal

package main

type Node struct {
    Data int
    Next *Node
}

func NewNode(data int) *Node {
    return &Node{Data: data, Next: nil}
}

package main

type LinkedList struct {
    Head *Node
}

func (list *LinkedList) Append(data int) {
    node := NewNode(data)
    
    if list.Head == nil {
        list.Head = node
    } else {
        last := list.Head
        for last.Next != nil {
            last = last.Next // find the node at the end
        }
        last.Next = node // set the new node as the last
    }
}

package main

type LinkedList struct {
    Head *Node
}

func (list *LinkedList) Append(data int) {
    node := NewNode(data)
    
    if list.Head == nil {
        list.Head = node
    } else {
        last := list.Head
        for last.Next != nil {
            last = last.Next // find the node at the end
        }
        last.Next = node // set the new node as the last
    }
}

package main

func (list *LinkedList) AddFirst(data int) {
    node := NewNode(data)
    
    if list.Head != nil {
        node.Next = list.Head // set head to the added value
    }
    list.Head = node
}

package main

func (list *LinkedList) AddFirst(data int) {
    node := NewNode(data)
    
    if list.Head != nil {
        node.Next = list.Head // set head to the added value
    }
    list.Head = node
}

package main

func (list *LinkedList) Delete(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
    }
}

package main

func (list *LinkedList) Delete(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
    }
}

package main

type LinkedList struct {
    Head *Node
}

func (list *LinkedList) Append(data int) {
    node := NewNode(data)
    
    if list.Head == nil {
        list.Head = node
    } else {
        last := list.Head
        for last.Next != nil {
            last = last.Next // find the node at the end
        }
        last.Next = node // set the new node as the last
    }
}

package main

func (list *LinkedList) AddFirst(data int) {
    node := NewNode(data)
    
    if list.Head != nil {
        node.Next = list.Head // set head to the added value
    }
    list.Head = node
}

package main

func (list *LinkedList) Delete(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
    }
}

Introduction to Linked Lists

Understanding the Concept

Implementing Linked Lists - Creating Node

Join the 1M+ learners on CodeSignal

Implementing Linked Lists - Append Method

Implementing Linked Lists - AddFirst Method

Implementing Linked Lists - Delete Method

Complexity Analysis

Summary and What's Next