The underlying implementation of golang linked list

1. Introduction to linked lists

A linked list is a data structure that consists of nodes. Each node contains data and a pointer to the next node. Compared with arrays, linked lists have the advantage of dynamic expansion because they do not need to allocate a continuous memory space at the beginning. Linked lists are divided into many types such as one-way linked lists, doubly linked lists, and circular linked lists.

In this article, we will discuss the underlying implementation of one-way linked lists in golang.

2. Implementation of one-way linked list

In golang, the underlying implementation of one-way linked list uses pointers to construct the relationship between nodes. Each node is defined as follows:

type Node struct {
    val interface{}
    next *Node
}

where val represents the value of the node, and next represents the pointer to the next node. The one-way linked list is defined as follows:

type SinglyLinkedList struct {
    head *Node
}

where head represents the head node of the linked list, that is, the first node.

Next, we will implement common operations of linked lists, including insertion, deletion, search and traversal.

1. Insertion operation

We first introduce two insertion operations: inserting at the head of the linked list and inserting at the end of the linked list.

The insertion operation at the head of the linked list is as follows:

func (l *SinglyLinkedList) InsertAtHead(val interface{}) {
    node := &Node{val: val}
    node.next = l.head
    l.head = node
}

Create a new node node, set the node value to val, and then point it to The original head node l.head, and the last update l.head can point to the new node.

The insertion operation at the end of the linked list is as follows:

func (l *SinglyLinkedList) InsertAtTail(val interface{}) {
    node := &Node{val: val}
    if l.head == nil {
        l.head = node
    } else {
        curr := l.head
        for curr.next != nil {
            curr = curr.next
        }
        curr.next = node
    }
}

First create a new node node. If the linked list is empty, set the new node as the head node. Otherwise, traverse the linked list starting from the head node until the last node curr.next == nil is found, and point its next to the new node.

2. Delete operation

The deletion operation includes deleting a specified node and deleting all specified nodes (same node value) in the linked list.

The operation to delete the specified node is as follows:

func (l *SinglyLinkedList) DeleteNode(node *Node) {
    curr := l.head
    if curr == node {
        l.head = curr.next
        return
    }

    for curr.next != nil {
        if curr.next == node {
            curr.next = curr.next.next
            return
        }
        curr = curr.next
    }
}

If the node to be deleted is the head node, just point l.head directly to its next node. Otherwise, traverse the linked list starting from the head node, find the node to be deleted (curr.next == node), and point its next to its next node.

The operation to delete all specified nodes in the linked list is as follows:

func (l *SinglyLinkedList) DeleteNodes(val interface{}) {
    for l.head != nil && l.head.val == val {
        l.head = l.head.next
    }

    curr := l.head
    for curr != nil {
        for curr.next != nil && curr.next.val == val {
            curr.next = curr.next.next
        }
        curr = curr.next
    }
}

If the value of the head node is val, delete the specified nodes in sequence. Then traverse the linked list starting from the head node and delete nodes with the same value in sequence.

3. Search operation

There are two main methods of search operation: searching for a node by specifying the node value and searching for the index of the node in the linked list.

The operation of finding a node by specifying the node value is as follows:

func (l *SinglyLinkedList) FindNode(val interface{}) *Node {
    curr := l.head
    for curr != nil {
        if curr.val == val {
            return curr
        }
        curr = curr.next
    }
    return nil
}

Traverse the linked list starting from the head node, compare the value of the node with the specified value val in turn, and return the node once it matches , otherwise return nil.

The operation to find the index of the node in the linked list is as follows:

func (l *SinglyLinkedList) FindIndex(node *Node) int {
    curr := l.head
    index := 0
    for curr != nil {
        if curr == node {
            return index
        }
        curr = curr.next
        index++
    }
    return -1
}

Traverse the linked list starting from the head node, and compare the nodes in sequence to see if they are the same as the specified node node. If they are the same, then Returns the index where the node is located, otherwise -1 is returned.

4. Traversal operation

There are two main methods of traversal operation: traversing all nodes and traversing the values ​​of all nodes.

The operation of traversing all nodes is as follows:

func (l *SinglyLinkedList) Traverse() []*Node {
    nodes := make([]*Node, 0)
    curr := l.head
    for curr != nil {
        nodes = append(nodes, curr)
        curr = curr.next
    }
    return nodes
}

Traverse the linked list starting from the head node, add all nodes to the nodes slice in order, and return the slice.

The operation of traversing the values ​​of all nodes is as follows:

func (l *SinglyLinkedList) TraverseValues() []interface{} {
    values := make([]interface{}, 0)
    curr := l.head
    for curr != nil {
        values = append(values, curr.val)
        curr = curr.next
    }

    return values
}

Traverse the linked list starting from the head node, add the values ​​of all nodes to the values slice in order, and return the slice.

3. Summary

In golang, the underlying implementation of a one-way linked list uses pointers to construct the relationship between nodes. By implementing common operations such as insertion, deletion, search, and traversal, we better understand the nature and advantages of linked lists, and also better understand how golang implements linked lists at the bottom level. In actual development, linked lists can be applied to many scenarios, such as LRU cache, inverted linked lists, etc.

The above is the detailed content of The underlying implementation of golang linked list. For more information, please follow other related articles on the PHP Chinese website!