How to implement doubly linked list in golang

Doubly linked list is a common data structure that can establish a two-way association between elements, making operations such as insertion, deletion and traversal in the linked list very efficient. In the Go language, the implementation of a doubly linked list is very simple. This article will introduce how to use Go to implement a doubly linked list.

A doubly linked list is a linked structure, each node of which contains three parts: the predecessor pointer prev, the successor pointer next and the data field data. In Go, we can define a struct to represent the nodes of a doubly linked list:

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

Among them, prev and next point to the predecessor and successor nodes of the current node respectively. data is the data stored by the node.

To implement a doubly linked list, we need to define a LinkedList type, which contains a pointer to the head node and tail node of the linked list, as well as the length of the linked list size:

type LinkedList struct {
    head *ListNode
    tail *ListNode
    size int
}

Let's implement the doubly linked list one by one of each operation.

Insert elements

Insert elements into a doubly linked list. There are three main situations:

1. Insert elements at the head of the linked list.
2. Insert an element at the end of the linked list.
3. Insert an element in the middle of the linked list.

In Go, we can define an Insert method to realize the above three situations:

func (list *LinkedList) Insert(data interface{}) {
    node := &ListNode{data: data}
    if list.head == nil {
        list.head = node
        list.tail = node
    } else {
        node.prev = list.tail
        list.tail.next = node
        list.tail = node
    }
    list.size++
}

First, we create a new node node to store the data to be inserted. If the linked list is empty, the new node will be used as the head node and tail node. Otherwise, insert the new node after the tail node and update the tail node pointer to the new node. Finally, the length of the linked list is increased by 1.

Deleting elements

Similar to inserting elements, deleting elements may also involve three situations:

1. Delete the head element of the linked list.
2. Delete the tail element of the linked list.
3. Delete the element in the middle of the linked list.

The following is an example implementation of the Delete method:

func (list *LinkedList) Delete(data interface{}) {
    node := list.find(data)
    if node != nil {
        if node.prev != nil {
            node.prev.next = node.next
        } else {
            list.head = node.next
        }
        if node.next != nil {
            node.next.prev = node.prev
        } else {
            list.tail = node.prev
        }
        list.size--
    }
}

func (list *LinkedList) find(data interface{}) *ListNode {
    node := list.head
    for node != nil && node.data != data {
        node = node.next
    }
    return node
}

First, we need to find the node node to be deleted, which is implemented through an auxiliary function find. If the node to be deleted is found, the pointers of the predecessor and successor nodes need to be updated based on the node's location. If the node to be deleted is the head node, update the head node pointer to the next node; if the node to be deleted is the tail node, update the tail node pointer to the previous node. Finally, reduce the length of the linked list by 1.

Traversing elements

Traversing a doubly linked list is very simple. You only need to start from the head node and continue traversing along the successor pointer next. Reverse traversal can start from the tail node and traverse along the predecessor pointer prev. The following are two methods to implement forward and reverse traversal respectively:

func (list *LinkedList) Traverse() []interface{} {
    result := make([]interface{}, list.size)
    node := list.head
    for i := 0; i < list.size; i++ {
        result[i] = node.data
        node = node.next
    }
    return result
}

func (list *LinkedList) ReverseTraverse() []interface{} {
    result := make([]interface{}, list.size)
    node := list.tail
    for i := 0; i < list.size; i++ {
        result[i] = node.data
        node = node.prev
    }
    return result
}

When traversing, we need to create a slice to save the traversal results, and then start from the head or tail node and traverse each node along the pointer , and stores the node's data into the slice.

Summary

Through the above code, we successfully implemented the basic operations of a doubly linked list. In practical applications, there are many extensions and optimizations to doubly linked lists, such as inserting or deleting elements at a certain position in the linked list, accessing elements through indexes, etc. Readers can conduct further study and practice as needed.

The code examples of this article have been uploaded to GitHub for readers’ reference: https://github.com/linjiawei123/golang-doubly-linked-list

The above is the detailed content of How to implement doubly linked list in golang. For more information, please follow other related articles on the PHP Chinese website!