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.
Comments
Post a Comment