DEV Community

loading...

Golang Linked List | Data Structure

divshekhar profile image Divyanshu Shekhar ・2 min read

What is a Linked List?

A Linked List is a linear Data Structure but not doesn’t have continuous memory addresses like Arrays or Slices. Linked Lists are Dynamic in nature.

In Golang Arrays we have to give size of the array while declaration, slice in golang uses arrays under the hood.

The Linked List is a Dynamic Data Structure, it occupies memory only for the stored data.

Golang Linked List Node Struct

type node struct {
    data int
    next *node
}

The Node Struct contains two fields one of type integer that contains the data and the “next” field that holds the memory address of the next Node.

Golang main Function

node := &node{data: 20}

Node struct is initialized with an ampersand sign in the above code (main Function), this is because the node variable will then be passed to the pushback method which will link this node in the linked list.

type linkedList struct {
    length int
    head   *node
    tail   *node
}

The Linked List Struct contains the length of the list, the head node, and the tail node.

The length field in the Linked List Struct stored the length of the linked list.

The Head field of Node Type stores the memory address of the head or the first node of the linked list.

The tail field in the Linked list of the Node type stored the memory address of the last node in the linked list.

Linked List Struct Initialization in Main Function.
main Function
list := linkedList{}

Length of the Linked List
Golang Length of Linked List

func (l linkedList) Len() int {
    return l.length
}

This method returns the Length of the Linked List.

Golang Linked List Display

func (l linkedList) Display() {
    for l.head != nil {
        fmt.Printf("%v -> ", l.head.data)
        l.head = l.head.next
    }
    fmt.Println()
}

In order to print the linked list, we have to traverse the whole linked list when the head of the link list becomes nil the loop exits.

Golang Linked List PushBack

func (l *linkedList) PushBack(n *node) {
    if l.head == nil {
        l.head = n
        l.tail = n
        l.length++
    } else {
        l.tail.next = n
        l.tail = n
        l.length++
    }
}

The PushBack Method takes a node as input and links it to the linked list.

If the linked list is empty, it makes the incoming node as the first node, and the head and tail both starts pointing at the node. The Length of the linked list is increased by 1.

When the head node is already present the else part executes and the tail node’s next field stores the memory address of the incoming node and the tail starts pointing at the node.

Main Function code for the pushback function.

list.PushBack(node)

Read more... https://divyanshushekhar.com/golang-linked-list/

Discussion (1)

Collapse
lemenendez profile image
leonidas menendez • Edited

Displaying the list but leaving the head as it is

func (l LinkedList) Display() {
n := l.head
for n != nil {
fmt.Printf("%v-->", n.data)
n = n.next
}
}

Forem Open with the Forem app