数据结构(1) 单链表简单实现

数据结构(1) 单链表简单实现

三月 19, 2019

单链表是一种链式存取的数据结构，用一组地址任意的存储单元存放线性表中的数据元素。链表中的数据是以结点来表示的，每个结点的构成：元素(数据元素的映象) + 指针(指示后继元素存储位置)，元素就是存储数据的存储单元，指针就是连接每个结点的地址数据

简述意思

链表是动态分配内存，时间复杂度O(1)。插入和删除速度快，内存利用率高，不会浪费内存(在需要空间的时候才会创建)，但是不能随机查找，只能遍历，且单链表只能根据一个指向下一个节点的指针往下遍历(next)。和数组对比，数组是静态分配内存，数组连续，可以根据下标进行定位(array[0])，可是数组的内存是连续的，比如在go里创建一个数组，需要给下标，且后续不可扩展(非slice切片)，数组可以随机查找，根据下标可以快速定位。

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
package main

import (
    "fmt"
)

type Object interface{}

// 节点 data值 next链节
type Node struct {
    data Object
    next *Node
}

// 链表 size长度 head首个 tail尾部
type List struct {
    size int
    head *Node
    tail *Node
}

// 初始化链表
func (list *List) Init() {
    list.size = 0
    list.head = nil
    list.tail = nil
}

// 添加元素方法 添加到最后节点最里部
func (list *List) Append(node *Node) bool {
    if node == nil {
        return false
    }

    node.next = nil

    if list.size == 0 {
        list.head = node
    } else {
        oldTail := list.tail
        oldTail.next = node
    }

    list.tail = node
    list.size++

    return true
}

// 插入到链表中(插入到尾部的话可以直接用Append，故这里不做处理)
func (list *List) Insert(i int, node *Node) bool {
    // 空间点、超出索引大小和空链表无法插入
    if node == nil || i > list.size || list.size == 0 {
        return false
    }

    if i == 0 {
        node.next = list.head
        list.head = node
    } else {
        // 上一个、前一个节点
        prev := list.head
        for j := 1; j < i; j++ {
            prev = prev.next
        }
        node.next = prev.next
        prev.next = node
    }
    list.size++

    return true
}

// 从链表中删除
func (list *List) Delete(i int) bool {
    if i > list.size || list.size == 0 {
        return false
    }

    if i == 0 {
        list.head = list.head.next
    } else {
        prev := list.head
        for j := 1; j < i; j++ {
            prev = prev.next
        }
        next := prev.next.next
        prev.next = next
    }
    list.size--

    return true
}

func main() {
    list := &List{}
    list.Init()
    node := &Node{
        data: 1,
        next: nil,
    }
    list.Append(node)
    fmt.Println(list) // &{1 0xc82000e0c0 0xc82000e0c0}
    node2 := &Node{
        data: 2,
        next: nil,
    }
    list.Append(node2)
    fmt.Println(list) // &{2 0xc82000e0c0 0xc82000e120}

    node3 := &Node{
        data: 3,
        next: nil,
    }
    list.Append(node3)

    node4 := &Node{
        data: 4,
        next: nil,
    }
    list.Insert(1, node4)

    list.Delete(1)

    fmt.Println(list.head.data) // 1
    fmt.Println(list.head.next.data) // 2
    fmt.Println(list.head.next.next.data) // 3
    // fmt.Println(list.head.next.next.next.data)
    // fmt.Println(list.tail.data)
    fmt.Println(list.tail.next) // nil
}

尾记

起风了，唯有努力生存

  1. 1. 简述意思
  2. 2. 代码实现
    1. 2.1. 尾记