Doubly linked lists in Go

Danielkvist
Nov 3 · 2 min read

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.

Danielkvist

Written by

#Golang dev and #Ukulelist. Looking for job.

Welcome to a place where words matter. On Medium, smart voices and original ideas take center stage - with no ads in sight. Watch
Follow all the topics you care about, and we’ll deliver the best stories for you to your homepage and inbox. Explore
Get unlimited access to the best stories on Medium — and support writers while you’re at it. Just $5/month. Upgrade