Linked List Implementation in Golang

1. Introduction

A Linked List is a foundational data structure, comprising a collection of nodes, where each node contains a value and a reference to the next node in the sequence. This design enables efficient insertion or removal of elements from any position within the sequence.

2. Implementation Steps

1. Define a Node type with two fields: data (to hold the actual value) and next (a pointer to the next node).

2. Define a LinkedList type with a head pointing to the first node.

3. Implement methods for adding elements (Append), deleting elements (DeleteWithValue), and displaying the list (Display).

3. Implementation in Golang

package main
import (
	"fmt"
)
type Node struct {
	data int
	next *Node
}
type LinkedList struct {
	head *Node
}
func (list *LinkedList) Append(data int) {
	newNode := &Node{data: data}
	if list.head == nil {
		list.head = newNode
		return
	}
	current := list.head
	for current.next != nil {
		current = current.next
	}
	current.next = newNode
}
func (list *LinkedList) DeleteWithValue(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 && current.next.data != data {
		current = current.next
	}
	if current.next != nil {
		current.next = current.next.next
	}
}
func (list *LinkedList) Display() {
	current := list.head
	for current != nil {
		fmt.Print(current.data, " -> ")
		current = current.next
	}
	fmt.Println("nil")
}
func main() {
	list := &LinkedList{}
	list.Append(1)
	list.Append(2)
	list.Append(3)
	list.Display()
	list.DeleteWithValue(2)
	list.Display()
}

Output:

1 -> 2 -> 3 -> nil
1 -> 3 -> nil

Explanation:

1. Node is a basic element of the Linked List, containing data and a reference to the next node.

2. LinkedList contains a head pointer which points to the first node in the list.

3. Append method: If the list is empty, the new node becomes the head. Otherwise, it traverses to the end of the list and adds the new node there.

4. DeleteWithValue method: If the head has the value to be deleted, it shifts the head to the next node. Otherwise, it traverses the list looking for the value, and if found, adjusts the next pointers to exclude the found node from the list.

5. Display method: It traverses the entire list, printing the data from each node.

6. In the main function, we create a Linked List, add some values, display it, delete a value, and display the list again to illustrate the workings of the list.

This Golang implementation of the Linked List serves as a foundation to understand more complex variations and operations possible with linked lists.