定义

链表通常跟数组对比来讲，最大不同从底层的存储结构上：数组需要连续的内存空间，对内存的要求比较高。而链表恰恰相反，它并不需要一块连续的内存空间，它通过“指针”将一组零散的内存块串联起来。

链表种类

单链表

头节点

尾节点，尾节点的next指针指向null。

双向链表

每个节点相比单链表都多存储了一个前驱指针，比较耗费内存。但是比单链表更便捷的插入和删除操作（单项链表插入和删除需要遍历两次链表，一次找到对应的值，第二次找到前驱指针，然后才能做插入或者删除操作。而双向链表，每个节点保持的前驱节点指针，直接就能找到前驱节点，更加高效），利用了空间换时间的设计思想。

循环链表

尾节点的next指针指向头节点。

双向循环链表

涉及设计思想

空间换时间，如缓存设计

讯享网

时间换空间

特点

1. 链表跟数组一样，支持查找，插入和删除。但是由于其存储结构不像数组那样要求连续内存，本身就是零散存储，所以插入和删除不需要维护连续性，非常快速，时间复杂度为O(1)。
2. 数组内存连续存储，借助CPU缓存机制，预读数组中的数据，所以访问更加高效。而链表分散存储，对cpu缓存机制并不友好。
3. 数组动态扩容比较耗时，而链表本身没有大小限制，天然支持动态扩容。
4. 数组仅存储数组区域，链表需要多存储指向指针，所以耗费的存储空间会翻倍。链表比数组更加多占用存储空间。对于空间很有要求的场景，适合选用数组。

缺点

不支持随机访问K个元素。因为地址不是连续存储，不像数组那样可以通过寻址公式（假设二维数组维度为m*n,则a[i][j]_adress = base_adress+(i*n+j)*type_size）直接定位到指定内存地址的值，需要通过首结点依次遍历，直到找到相应的节点。所以随机访问并不高效，时间复杂度O(n)。

时间复杂度

应用

LRU缓存淘汰策略

维护一个有序单链表，越靠近队尾位置，是越早被访问的数据。当有访问一个数据时，先遍历链表：

1. 此链表存在链表中时，直接删除此节点，并把此节点移动到队首。
2. 当此链表不存在此节点时：

• 此链表缓存未满：直接将此数组插入到链表队首。
• 此链表缓存已满：直接删除掉队尾结点，把新数据插入到队首结点。

单链表实现

package main import ( "fmt" ) type LinkNode struct { next *LinkNode value interface{} } type LinkedList struct { head *LinkNode length uint } func NewLinkNode(v interface{}) *LinkNode { return &LinkNode{ next: nil, value: v, } } func (linkNode *LinkNode) GetNext() *LinkNode { return linkNode.next } func (linkNode *LinkNode) GetValue() interface{} { return linkNode.value } func NewLinkedList() *LinkedList { return &LinkedList{ head: NewLinkNode(0), length: 0, } } //在某个节点后面插入节点 func (this *LinkedList) InsertAfter(p *LinkNode, v interface{}) bool { if p == nil { return false } newNode := NewLinkNode(v) oldNode := p.next p.next = newNode newNode.next = oldNode this.length++ return true } //在某个节点前面插入节点 func (this *LinkedList) InsertBefore(p *LinkNode, v interface{}) bool { if p == nil || this.head == p { return false } pre := &LinkNode{} cur := this.head for cur.next != nil { if cur.next == p { break } pre = cur cur = cur.next } if pre == nil { return false } newNode := NewLinkNode(v) pre.next = newNode newNode = cur this.length++ return true } //在链表头部插入节点 func (this *LinkedList) InertToHead(v interface{}) bool { return this.InsertAfter(this.head, v) } //在链表尾部插入节点 func (this *LinkedList) InsertToTail(v interface{}) bool { cur := this.head for cur.next != nil { cur = cur.next } return this.InsertAfter(cur, v) } //通过索引查找节点 func (this *LinkedList) FindByIndex(index uint) *LinkNode { if index > this.length { return nil } cur := this.head for i:=uint(0);i<index;i++ { cur = cur.next } return cur } //删除传入的节点 func (this *LinkedList) DeleteNode(p *LinkNode) bool { if p == nil { return false } if this.head == p { this.head = p.next this.length-- return true } cur := this.head.next pre := this.head for cur != nil { if cur == p { break } pre = cur cur = cur.next } pre.next = p.next p = nil this.length-- return true } //打印链表 func (this *LinkedList) PrintLinkedList() (values string) { cur := this.head for cur != nil { values += fmt.Sprintf("%+v", cur.GetValue()) cur = cur.next if cur != nil { values += "->" } } fmt.Printf("linkedList : {%v}\n",values) return values } func main() { n1 := NewLinkNode("a") n2 := NewLinkNode("b") n3 := NewLinkNode("c") n4 := NewLinkNode("d") n1.next = n2 n2.next = n3 n3.next = n4 linkedList := NewLinkedList() linkedList.head = n1 linkedList.length++ linkedList.PrintLinkedList() linkedList.InsertAfter(n1, "insert_n1_after") linkedList.PrintLinkedList() linkedList.InsertBefore(n3, "insert_n3_before") linkedList.PrintLinkedList() linkedList.DeleteNode(n1) linkedList.PrintLinkedList() linkedList.DeleteNode(n3) linkedList.PrintLinkedList() } 

回文字符串判断

讯享网package main import "fmt" func main() { s := "abcba" //双指针 header := 0 tail := len(s)-1 //小心数组越界 for header<=tail { if s[header] != s[tail] { fmt.Println("不是回文字符串") return } header++ tail-- } fmt.Println("是回文字符串") return } // todo 链表快慢指针版本 

链表反转

package main import "fmt" type LinkedNode struct { value int nextNode *LinkedNode } // 非递归实现 func ReverseLikedNode(head *LinkedNode) *LinkedNode { // 先声明两个变量 // 前一个节点 var preNode *LinkedNode preNode = nil // 后一个节点 var nextNode *LinkedNode nextNode = nil for head != nil { // 保存头节点的下一个节点， nextNode = head.nextNode // 实现翻转 head.nextNode = preNode // 更新前一个节点 preNode = head // 更新头节点 head = nextNode } return preNode } // 递归实现：利用递归调用栈，递归循环后本身就是倒序输出，仅需要把倒序的的每个初始化成链表即可。 var newLinked *LinkedNode // 反转后新链表的头节点 var endLinked *LinkedNode // 新链表的尾节点， 也可以理解为新链表双指针：newLinked=>头指针，endLinked=>尾指针 func rev(node *LinkedNode) { if node == nil { return } if node.nextNode == nil { // 最后一个元素，先初始化newLinked头节点 endLinked = node newLinked = endLinked return } //fmt.Printf("node : %v \n", node) // 传入的是当前节点的下一个节点 rev(node.nextNode) //fmt.Printf("linkedNode : %v\n", node) // 回溯 // node为倒数第二个节点开始 endLinked.nextNode = node // 指针后移 endLinked = endLinked.nextNode // 最后节点置空，防止循环链表产生 endLinked.nextNode = nil } func printLinkedNode(head *LinkedNode) { for head != nil { //fmt.Print(head.value, "\t") fmt.Println(head) head = head.nextNode } fmt.Println() } func main() { node1 := new(LinkedNode) node1.value = 1 node2 := new(LinkedNode) node2.value = 2 node3 := new(LinkedNode) node3.value = 3 node4 := new(LinkedNode) node4.value = 4 node1.nextNode = node2 node2.nextNode = node3 node3.nextNode = node4 //printLinkedNode(node1) rev(node1) printLinkedNode(newLinked) fmt.Printf("linked: %+v",newLinked) //head := ReverseLikedNode(node1) //printLinkedNode(head) } //package main // 链表数据结构 //type LinkedList struct { // value interface{} // Next *LinkedList //} // //var newLinkedList LinkedList // //func resv(node LinkedList) { // if node.value == nil { // return // } // if node.Next == nil { // newLinkedList = node // return // } // resv(*node.Next) // newLinkedList.Next = &node //} // //func main() { // l := LinkedList{ // value: nil, // Next: nil, // } // // //} 

链表其他操作

讯享网package main import ( "fmt" ) type LinkedNode struct { value int nextNode *LinkedNode } type LinkedList struct { head *LinkedNode } func ReverseLikedNode(head *LinkedNode) *LinkedNode { // 先声明两个变量 // 前一个节点 var preNode *LinkedNode preNode = nil // 后一个节点 var nextNode *LinkedNode nextNode = nil for head != nil { // 保存头节点的下一个节点， nextNode = head.nextNode // 实现翻转 head.nextNode = preNode // 更新前一个节点 preNode = head // 更新头节点 head = nextNode } return preNode } var newLinked *LinkedNode var endLinked *LinkedNode func rev(node *LinkedNode) { if node == nil { return } if node.nextNode == nil { endLinked = node newLinked = endLinked return } //fmt.Printf("node : %v \n", node) rev(node.nextNode) //fmt.Printf("linkedNode : %v\n", node) endLinked.nextNode = node endLinked = node endLinked.nextNode = nil } func (link *LinkedNode) isCy() bool { if link == nil || link.nextNode == nil { return false } if link.nextNode != nil { head := link for head.nextNode != nil { slow := head.nextNode fast := head.nextNode.nextNode if slow != nil || fast != nil { if slow == fast { return true } } head = head.nextNode } } return false } // head 为哨兵节点，不存储任何值 func mergeSortLinked(sortList1, sortList2 *LinkedList) (linkedList *LinkedList) { if sortList1 == nil || sortList1.head == nil || sortList1.head.nextNode == nil { return sortList2 } if sortList2 == nil || sortList2.head == nil || sortList2.head.nextNode == nil { return sortList1 } linkedList = &LinkedList{head:&LinkedNode{}} curl := linkedList.head head1 := sortList1.head.nextNode head2 := sortList2.head.nextNode for head1 != nil && head2 != nil { if head1.value < head2.value { curl.nextNode = head1 head1 = head1.nextNode } else { curl.nextNode = head2 head2 = head2.nextNode } curl = curl.nextNode } if head1 == nil { curl.nextNode = head1 } else { curl.nextNode = head2 } return linkedList } func (this *LinkedList) delLastN(n int) bool { if n <= 0 || this.head == nil || this.head.nextNode == nil { return false } slow, fast := this.head, this.head var i int for i=1; i<=n && fast!=nil ; i++ { fast = fast.nextNode } if i != n { return false } for fast != nil && fast.nextNode != nil { slow = slow.nextNode fast = fast.nextNode } slow.nextNode = slow.nextNode.nextNode return true } func (this *LinkedList) getMidNode() (mid *LinkedNode){ if this.head == nil || this.head.nextNode == nil { return } slow := this.head fast := this.head for fast != nil && fast.nextNode != nil { slow = slow.nextNode fast = fast.nextNode.nextNode } mid = slow return } func printLinkedList(list *LinkedList) { if list.head == nil || list.head.nextNode == nil { return } head := list.head str := "" for head != nil { str += fmt.Sprintf( "%+v", head.value) if head.nextNode != nil { str += "->" } head = head.nextNode } fmt.Println(str) } func main() { node1 := new(LinkedNode) node1.value = 1 node2 := new(LinkedNode) node2.value = 3 node3 := new(LinkedNode) node3.value = 4 node4 := new(LinkedNode) node4.value = 7 node1.nextNode = node2 node2.nextNode = node3 //node3.nextNode = node4 //printLinkedNode(node1) //head := ReverseLikedNode(node1) //printLinkedNode(head) //rev(node1) //printLinkedNode(newLinked) //node3.nextNode = node1 //b := node1.isCy() //fmt.Println(b) node5 := new(LinkedNode) node5.value = 2 node6 := new(LinkedNode) node6.value = 5 node7 := new(LinkedNode) node7.value = 6 node8 := new(LinkedNode) node8.value = 8 node5.nextNode = node6 node6.nextNode = node7 node7.nextNode = node8 // 哨兵链表 LinkedList1 := &LinkedList{head:&LinkedNode{nextNode:node1}} LinkedList2 := &LinkedList{head:&LinkedNode{nextNode:node5}} list := mergeSortLinked(LinkedList1, LinkedList2) printLinkedList(list) node := LinkedList1.getMidNode() fmt.Println("mid :",node) //bool := list.delLastN(13) //fmt.Println("list delLastN : ", bool) //printLinkedList(list) }