Doubly Linked List Implementation in Golang

1. Introduction

A Doubly Linked List is a type of linked list in which each node contains a data part and two pointers. One pointer points to the next node in the list, and the other points to the previous node. This two-way linkage allows for more efficient traversal in both directions, as opposed to a singly linked list.

2. Implementation Steps

1. Define a Node type with three fields: data (to store the actual value), next (a pointer to the next node), and prev (a pointer to the previous node).

2. Define a DoublyLinkedList type with a head and a tail pointer.

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

3. Implementation in Golang

package main
import (
	"fmt"
)
type Node struct {
	data int
	next *Node
	prev *Node
}
type DoublyLinkedList struct {
	head *Node
	tail *Node
}
func (list *DoublyLinkedList) Append(data int) {
	newNode := &Node{data: data}
	if list.head == nil {
		list.head = newNode
		list.tail = newNode
		return
	}
	newNode.prev = list.tail
	list.tail.next = newNode
	list.tail = newNode
}
func (list *DoublyLinkedList) DeleteWithValue(data int) {
	current := list.head
	for current != nil {
		if current.data == data {
			if current.prev != nil {
				current.prev.next = current.next
			} else {
				list.head = current.next
			}
			if current.next != nil {
				current.next.prev = current.prev
			} else {
				list.tail = current.prev
			}
			return
		}
		current = current.next
	}
}
func (list *DoublyLinkedList) Display() {
	current := list.head
	for current != nil {
		fmt.Print(current.data, " <-> ")
		current = current.next
	}
	fmt.Println("nil")
}
func main() {
	list := &DoublyLinkedList{}
	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 the basic element of the Doubly Linked List, containing data, a next pointer to the next node, and a prev pointer to the previous node.

2. DoublyLinkedList has two pointers: head pointing to the first node and tail pointing to the last node.

3. Append method: Adds a new node at the end of the list, adjusting the previous tail's next pointer and the new node's prev pointer accordingly.

4. DeleteWithValue method: Traverses the list to find the node with the desired data. Once found, it adjusts the neighboring nodes' pointers to exclude the target node from the list.

5. Display method: Prints out the data in the list from start to end.

6. The main function demonstrates adding nodes to the list, displaying its contents, removing a node, and displaying the updated list.

The Doubly Linked List provides greater flexibility over a singly linked list due to its bidirectional pointers, facilitating more diverse operations.