Doubly Linked List Implementation in Go

Hi there DEV.to community!

As a second part of my previous post (linked in the series above), here we will implement a doubly linked list. A doubly linked list is just as a singly linked list with one difference. Each node refers to both its next node and its previous node. Thus we may move forward in the list using a function called GetNext and move to the previous node with a function called GetPrev.

Image source: GeeksforGeeks

Before we start here is the structure I'd like to organize my codes like:

project
├── doubly_linked_list
│   ├── node.go
│   └── list.go
└── main.go

Doubly Node

To define a doubly node in Go, the first thing we need to do is creating a struct in the node.go file:

type DoublyNode struct {
    data interface{}
    next *DoublyNode
    prev *DoublyNode
}

A doubly node holds three properties:

• A data property with interface{} type so it can hold any data type
• A next property that holds a pointer to another DoublyNode
• A prev property that holds a pointer to another DoublyNode

Just as before we need to have some functions to utilize this struct. The first function we will define is a constructor that creates a new DoublyNode:

func NewDoublyNode(data interface{}) *DoublyNode {
    return &DoublyNode{data: data}
}

This function creates a DoublyNode and returns its reference.

Then we will define setters and getters for all the properties (data, next and prev):

func (n *DoublyNode) SetData(data interface{}) {
    n.data = data
}

func (n *DoublyNode) GetData() interface{} {
    return n.data
}

func (n *DoublyNode) SetNext(next *DoublyNode) {
    n.next = next
}

func (n *DoublyNode) GetNext() (*DoublyNode, error) {
    if n.next == nil {
        return nil, errors.New("no next node")
    }
    return n.next, nil
}

func (n *DoublyNode) SetPrev(prev *DoublyNode) {
    n.prev = prev
}

func (n *DoublyNode) GetPrev() (*DoublyNode, error) {
    if n.prev == nil {
        return nil, errors.New("no previous node")
    }
    return n.prev, nil
}

Here is the explanation for each function:

• SetData(data interface{})
  • Receives a data argument of interface{} type and sets it as the data of the node.
• GetData
  • Returns the data of the node
• SetNext(next *DoublyNode)
  • Receives a reference to node and sets it as the current node's next
• Getnext()
  • Check if the next property of the node is nil to return an error,
  • If the next property is not nil, it returns the next property of the node.
• SetPrev(next *DoublyNode)
  • Receives a reference to node and sets it as the current node's prev
• GetPrev()
  • Check if the prev property of the node is nil to return an error,
  • If the prev property is not nil, it returns the prev property of the node.

And my beloved ToString function to make sure each time I know how to retrieve the data of the node as a string:

func (n *DoublyNode) ToString() string {
    return n.data.(string)
}

List

Now that we have our node defined it is time to define the list itself. I would put these codes inside the list.go file:

type DoublyLinkedList struct {
    head  *DoublyNode
    last  *DoublyNode
    count int
}

The DoublyLinkedList is no different than the SinglyLinkedList from the previous post. A doubly linked list usually differs in its node's structure.

This struct holds up 3 properties:

• head to hold the first node of the list
• last to hold the last node of the list
• count to hold the number of nodes added inside the list

Now the functions that we need to utilize the struct.

The first one as always is the function to create a new doubly linked list:

func NewDoublyLinkedList() *DoublyLinkedList {
    return &DoublyLinkedList{}
}

Now the most important function to attach a node to our list:

func (l *DoublyLinkedList) AttachNode(node *DoublyNode) {
    if l.head == nil {
        l.head = node
    } else {
        l.last.SetNext(node)
        node.SetPrev(l.last)
    }
    l.last = node
    l.count++
}

This function receives a node and checks if the list's head is empty adds it as the head of the list and if not sets the next of the last node in the list as the received node and sets the received node's prev as the current last node in the list.

Then finally sets the last node of the list as the received node and increases the count of the list by one.

I will a function (just as before) to receive a data argument and turn it into a node and send it to the AttachNode function so it becomes a little easier to add nodes:

func (l *DoublyLinkedList) Add(data interface{}) {
    l.AttachNode(NewDoublyNode(data))
}

A function to return the count of the list:

func (l *DoublyLinkedList) Count() int {
    return l.count
}

If you've read the previous article you know that I like to create functions named after the accessors of the next and prev of the nodes inside the list so it becomes a bit more consistent when accessing the data inside list:

func (l *DoublyLinkedList) GetNext() (*DoublyNode, error) {
    if l.head == nil {
        return nil, errors.New("list is empty")
    }
    return l.head, nil
}

func (l *DoublyLinkedList) GetPrev() (*DoublyNode, error) {
    if l.last == nil {
        return nil, errors.New("list is empty")
    }
    return l.last, nil
}

The GetNext function checks if the head is nil inside the list to return an error. And if not returns the first node of the list.

The GetPrev function checks if the last is nil inside the list to return an error. And if not returns the last node of the list.

A GetByIndex function is always recommended to make it possible to access the nodes by their index inside the list:

func (l *DoublyLinkedList) GetByIndex(index int) (*DoublyNode, error) {
    if l.head == nil {
        return nil, errors.New("list is empty")
    }
    if index+1 > l.count {
        return nil, errors.New("index out of range")
    }
    node, _ := l.GetNext()
    for i := 0; i < index; i++ {
        node, _ = node.GetNext()
    }
    return node, nil
}

This function checks if the head is nil to return an error. Then checks if the index+1 is bigger than the count of the list to return an error since we consider the indices starting from 0.

Then set the head of the list as node and loop for 1 less than the provided the index so it moves forward as intended by replacing the node as the current node's next. Finally returns the node with no error.

Testing

To test the just written code you may do so in your main function:

func main() {
    list := doubly_linked_list.NewDoublyLinkedList()

    list.Add("One")
    list.Add("Two")
    list.Add("Three")
    list.Add("Four")

    first, err := list.GetNext()
    if err != nil {
        panic(err)
    }

    second, err := first.GetNext()
    if err != nil {
        panic(err)
    }

    getBackToFirst, err := second.GetPrev()
    if err != nil {
        panic(err)
    }

    fmt.Println(getBackToFirst.ToString()) // One
}

Or by using the GetByIndex function:

func main() {
    list := doubly_linked_list.NewDoublyLinkedList()

    list.Add("One")
    list.Add("Two")
    list.Add("Three")
    list.Add("Four")

    n, err := list.GetByIndex(3)

    if err != nil {
        panic(err)
    }

    fmt.Println(n.ToString()) // Four
}

---

BTW! Check out my free Node.js Essentials E-book here:

NodeJS Essentials | Free E-Book

Adnan Babakan (he/him) ・ Sep 11 '20

#node #javascript #books

Feel free to contact me if you have any questions or suggestions.