Doubly linked lists in Go
Like Linked lists, Doubly linked lists are a very simple data structure whose definition from Wikipedia is:
A Doubly linked list is a linked data structure that consists of a set of sequentially linked records called nodes. Each Node contains three fields: two link fields (references to the previous and to the next Node in the sequence of nodes) and one data field.
Basically now our Node struct will have a value, a link to the next Node in the list and another link to the previous one.
Doubly linked lists have an important difference over Linked lists: they can be traversed in forward or backwards directions.
With Doubly linked lists is also more easy insert new Nodes before existing ones.
But Doubly linked lists are not perfect and have disadvantages over Linked lists:
- Each Node requires extra space due to the extra pointer.
- All operations become a little more complicated because you have to manage now the extra pointer.
To implement a Doubly linked list in Go we need to start defining it’s basic component: the Node.
Defining a Node
Type Node struct {
value int // Our data
pre *Node // Pointer to the previous Node
next *Node // Pointer to the next Node
}Defining a Doubly linked list
Type DoublyLinkedList struct {
head *Node // The first node
tail *Node // The last node
length int // The number of nodes
}Append
func (dl *DoublyLinkedList) Append(n *Node) {
if dl.length == 0 {
dl.first = n
dl.last = n
dl.length++
return
} lastNode := dl.last dl.last = n
dl.last.pre = lastNode
lastNode.next = n
dl.length++
}
Prepend
func (dl *DoublyLinkedList) Prepend(n *Node) {
if dl.length == 0 {
dl.first = n
dl.last = n
dl.length++
return
} preFirstNode := dl.first dl.first = n
dl.first.next = preFirstNode
preFirstNode.pre = n
dl.length++
}
Lookup
func (dl *DoublyLinkedList) Lookup() []int {
if dl.length == 0 {
return nil
} var nodes []int
node := dl.first for node != nil {
nodes = append(nodes, node.value)
node = node.next
} return nodes
}
Delete
func (dl *DoublyLinkedList) Delete(v int) {
if dl.length == 0 {
return
} if dl.first.value == v {
dl.first = dl.first.next
dl.first.pre = nil
dl.length--
return
} if dl.last.value == v {
prePreLastNode := dl.last.pre
dl.last = prePreLastNode
prePreLastNode.next = nil
dl.length--
return
} var prevNode *Node
var nextNode *Node
node := dl.first for node.value != v {
if node == nil {
return
} prevNode = node
node = node.next
nextNode = node.next
} prevNode.next = node.next
nextNode.pre = prevNode
dl.length--
}
Go playground
You can find all the code here.
Originally published at https://dkvist.com.
