单链表是一种链式存取的数据结构,用一组地址任意的存储单元存放线性表中的数据元素。链表中的数据是以结点来表示的,每个结点的构成:元素(数据元素的映象) + 指针(指示后继元素存储位置),元素就是存储数据的存储单元,指针就是连接每个结点的地址数据
简述意思
链表是动态分配内存,时间复杂度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{}
type Node struct { data Object next *Node }
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 }
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) node2 := &Node{ data: 2, next: nil, } list.Append(node2) fmt.Println(list)
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) fmt.Println(list.head.next.data) fmt.Println(list.head.next.next.data) fmt.Println(list.tail.next) }
|
尾记
起风了,唯有努力生存