数据结构:单链接列表
#go #linkedlist #数据结构 #singlylinkedlist

原始文章可在我的网站上找到:https://promisefemi.vercel.app/blog/data-structures-singly-linked-list

虚幻的数据结构,在本系列中,我将在GO编程语言中解释各自的数据结构及其各自的实现。

链接列表是一个非常简单的数据结构,通常将它们与数组进行比较,但是不仅在实施方式上,而且在它们如何在引擎盖下工作。

都存在明显的差异。

阵列的值彼此存储在内存中,从而很容易通过直接接触到索引来找到特定值。

这是阵列的视觉表示 - 200,201,202â表示内存中的空间

Image source: https://www.geeksforgeeks.org

图像来源:https://www.geeksforgeeks.org

另一方面,链接列表在节点中排列,每个节点指向内存中的下一个节点,内存中的值可能不会彼此接近。

Image source: https://www.geeksforgeeks.org

图像来源:https://www.geeksforgeeks.org

从头部(第一个节点)指向下一个节点,该节点指向下一个节点,依此类推。

这是大多数人开始问为什么他们应该使用链接列表而不是仅使用数组,从而节省压力的时候。但是链接列表对于存储有序数据和其他形式的链接列表(例如双重链接列表)特别有用

好的谈话,向我展示代码

实施单链接列表

实现单一链接列表非常简单(相信我ð)

首先,我们需要创建链接列表的结构

package main

type linkedList struct {
// value can be whatever datatype fits your particular scenario
    value string
    next  *linkedList
}

在上面的示例中,我们创建了一个具有值和下一个字段的新结构类型,值字段是当前节点的值,下一个字段指向链接列表上的下一个节点。让我们初始化一个新的linkedlist

func main(){
    list := new(linkedList)
}

这就是(不是特别),这就是链接列表的结构所需的全部。现在,让我们谈论将新节点插入链接列表中。

插入新节点

要将一个新节点插入链接列表中,我们必须浏览链接列表,直到找到最后一个节点,然后我们只将新节点添加到最后一个位置。如果您感到困惑,让我用代码解释。

func (node *linkedList) insert(text string){
        // first we create a temporary value for our new node
        tempNode :=  &linkedList{value: text, next: nil}
        // remember that the next pointer in the last node is always nil until it points to another node
        if node == nil{
        // if this is a head node and it is nill, make the current tempNode the head
            node = tempNode
        }else{          
                currentNode :=  node
                // go through every node until we get to the last node,             
                for currentNode.next != nil{
                    // check if it is the last node, if not move to the next 
                    currentNode =  currentNode.next
                }
            // when we get to the last node, place the new node we are creating
            currentNode.next = tempNode
        }
}

现在,当我们返回主()时,我们将调用插入方法将新节点添加到我们的链接列表

func main(){
    list := new(linkedList)
    list.insert("Apple")
    list.insert("Oranges")
    list.insert("Strawberries")
}

在这一点上,您可能就像是的,我们一直在做所有事情担心我得到了你。

显示值

让我们添加一种通过每个节点循环以打印其值的方法。

func (node *linkedList) print(){
// start from the first node
    currentNode := node
    // loop through each node, making sure it is not nil
    for currentNode != nil{
        //print the value out
        fmt.Printf("%s -> ", currentNode.value)
        //move to the next node
        currentNode = currentNode.next
    }
}

现在都在一起了

package main

type linkedList struct {
// value can be whatever datatype fits your particular scenario
    value string
    next  *linkedList
}

func (node *linkedList) insert(text string){
        // first we create a temporary value for our new node
        tempNode :=  &linkedList{value: text, next: nil}
        // remember that the next pointer in the last node is always nil until it points to another node
        if node == nil{
        // if this is a head node and it is nill, make the current tempNode the head
            node = tempNode
        }else{          
                currentNode :=  node
                // go through every node until we get to the last node,             
                for currentNode.next != nil{
                    // check if it is the last node, if not move to the next 
                    currentNode =  currentNode.next
                }
            // when we get to the last node, place the new node we are creating
            currentNode.next = tempNode
        }
} 

func (node *linkedList) print(){
// start from the first node
    currentNode := node
    // loop through each node, making sure it is not nil
    for currentNode != nil{
        //print the value out
        fmt.Printf("%s -> ", currentNode.value)
        //move to the next node
        currentNode = currentNode.next
    }
}

func main(){
    list := new(linkedList)
    list.insert("Apple")
    list.insert("Oranges")
    list.insert("Strawberries")

    list.print()
}

完整的所有这些,让我们的用户可以在将新节点添加到链接列表中并打印整个链接列表
,从而使其变得更加有趣

package main

import (
    "fmt"
    "log"
    "os"
)

type linkedList struct {
    // value can be whatever datatype fits your particular scenario
    value string
    next  *linkedList
}

func (node *linkedList) insert(text string) {
    // first we create a temporary value for our new node
    tempNode := &linkedList{value: text, next: nil}
    // remember that the next pointer in the last node is always nil until it points to another node
    if node == nil {
        // if this is a head node and it is nill, make the current tempNode the head
        node = tempNode
    } else {
        currentNode := node
        // go through every node until we get to the last node,
        for currentNode.next != nil {
            // check if it is the last node, if not move to the next
            currentNode = currentNode.next
        }
        // when we get to the last node, place the new node we are creating
        currentNode.next = tempNode
    }
}

func (node *linkedList) print() {
    // start from the first node
    currentNode := node
    // loop through each node, making sure it is not nil
    for currentNode != nil {
        //print the value out
        fmt.Printf("%s -> ", currentNode.value)
        //move to the next node
        currentNode = currentNode.next
    }
    fmt.Println("")
}

func main() {
    list := new(linkedList)

    for {
        var selected string
        fmt.Println("(1) enter a new item")
        fmt.Println("(2) print list")
        _, err := fmt.Scanln(&selected)
        if err != nil {
            log.Fatalln(err)
        }

        switch selected {
        case "1":
            var item string
            _, err := fmt.Scanln(&item)
            if err != nil {
                log.Fatalln(err)
            }
            list.insert(item)
        case "2":
            list.print()
        default:
            os.Exit(0)
        }
    }
}

hurray !!!通过简单地将值传递给方法(称为功课)来从链接列表中的节点。

本文中的代码可用here

感谢您的阅读,希望下次再次见到您,请分享。