programming

How to implement a single double linked list in Golang

  • avatar
    by Ihsan
  • 9 Apr 2021
  • 2 minutes

Basic Definition

If you’ve read and read about the Linked List, you can first read Santekno’s post Single Linked List and Double Linked List

In contrast to the previous implementation using C ++ language, now we use the language GO alias rolas usually people say. Actually not too far and complicated to apply it because the script from Golang is easier and concise.

Single Linked List

package main

type List struct {
	head *Node
	tail *Node
}

func (l *List) First() *Node {
	return l.head
}

func (l *List) Push(value int) {
	node := &Node{value: value}
	if l.head == nil {
		l.head = node
	} else {
		l.tail.next = node
	}
	l.tail = node
}

type Node struct {
	value int
	next  *Node
}

func (n *Node) Next() *Node {
	return n.next
}

func main() {
	l := &List{}
	l.Push(1)
	l.Push(2)
	l.Push(3)

	n := l.First()
	for {
		println(n.value)
		n = n.Next()
		if n == nil {
			break
		}
	}
}

Single Linked List If we conclude it only has a next () `node. This is a simple example of a single linked list.

Double Linked List

package main

type List struct {
	head *Node
	tail *Node
}

func (l *List) First() *Node {
	return l.head
}

func (l *List) Last() *Node {
	return l.tail
}

func (l *List) Push(value int) {
	node := &Node{value: value}
	if l.head == nil {
		l.head = node
	} else {
		l.tail.next = node
		node.prev = l.tail
	}
	l.tail = node
}

type Node struct {
	value int
	next  *Node
	prev  *Node
}

func (n *Node) Next() *Node {
	return n.next
}

func (n *Node) Prev() *Node {
	return n.prev
}

func main() {
	l := &List{}
	l.Push(1)
	l.Push(2)
	l.Push(3)

	n := l.First()
	for {
		println(n.value)
		n = n.Next()
		if n == nil {
			break
		}
	}

	n = l.Last()
	for {
		println(n.value)
		n = n.Prev()
		if n == nil {
			break
		}
	}
}

What distinguishes from single and double linked list? That is, in the Double Linked List the node can know before and after the node being intended. So that we add the `prev () method so that the previous node we know the address of the memory.

Library Go

If you want to learn more related to Linked List can try using the Library Go that has been provided [here] (https://golang.org/pkg/container/list/). This is a library that can make it easier for you to implement the Single Linked List or Double Linked List.

Previous post
Getting to Know Pointers in Golang
Next post
How to Implement Stack in Golang
comments powered by Disqus