算法与数据结构—链表

链表的种类很多，常用的如：单链表，双向链表，循环链表

特点

  • 无需连续内存
  • 插入删除快速，时间 O(1)
  • 根据k访问元素低效，需遍历链表，时间O(n)

由于数组是连续存储的，可以充分利用CPU缓存机制，预读。而链表非连续存储则不行。 数组的大小总是固定的，预先申请一片连续内存。如果不够还需重新申请更大的内存，再把数据拷贝过去。 如果对链表过频繁的插入和删除，会造成内存频繁的申请和释放，容易造成内存碎片。

链表的插入、删除操作，需要对插入第一个结点和插入、删除操作，需要首尾节点重点考虑。 引入哨兵节点，简化编程。哨兵结点是不存储数据的。让节点的逻辑统一。 在软件开发中，边界最易初bug，需要重点留意。链表为空时，链表只有一个节点时，处理头节点和尾节点还能否正常

举例画图，辅助思考 多练多写，没有捷径

常见链表操作：最好代码写出来

  1. 单链表反转(把链表头变成尾，尾变成头)
  2. 链表中环的检测
  3. 两个有序链表合并
  4. 删除链表倒数第n个节点 (如果一次遍历实现删除. count = n + ( count - n) )
  5. 求链表的中间节点 (fast每次两步。slow每次一步，fast到头，slow刚好走一半)

链表中环的检测

检测单链表中是否存在环。 方法：用快指针fast, 每次走2步。slow指针每次走1步。同时从头开始走，若发fast与slow相遇，则存在环。若最终若快指针指向null，则无环。 原因：若有环，快指针先行进环，在环中绕圈，慢指针后入环，也在环中绕圈，由于快指针每次比慢指针多走一步，意味着两个指针在环中的位置每次都缩短一步，所以若有环，两个指针在环中必能相遇。

LRU

利用链表实现缓存淘汰算法LRU

如果已经被缓存在链表中了, 则移动到链表前面；

如果不在链表中，链表没满则在头部插入，满了则先删除尾部数据，再开头插入。可以在引入hash表记录数据位置，把访问时间降为O(1)

操作

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

type LinkedList struct {
	head *Node
	tail *Node
}

func (l *LinkedList) PrintAll() {
	for p := l.head; p != nil; p = p.next {
		fmt.Print(p.Data, " ")
	}
	fmt.Println()
}

func (l *LinkedList) PrintTail() {
	fmt.Println(l.tail.Data)
}

在链表尾部插入节点

// 尾部追加
func (l *LinkedList) Append(data interface{}) {
	node := &Node{
		Data: data,
		next: nil,
	}
	if l.head == nil {
		l.head = node
		l.tail = node
	}

	l.tail.next = node
	l.tail = node
}

删除节点

// 删除节点
func (l *LinkedList) Del(data interface{}) {
	prevNode := l.head
	for p := l.head; p != nil; p = p.next {
		if p.Data == data {
			switch {
			case p == l.head:
				l.head = l.head.next
			case p == l.tail:
				l.tail = prevNode
				prevNode.next = p.next
			default:
				prevNode.next = p.next
			}
			p = nil
			return
		}
		prevNode = p
	}
}

单链表反转(把链表头变成尾，尾变成头)

// 单链表反转
// p1 -> p2 -> p3-> p4  =>  p4 -> p3 -> p2 -> p1
func (l *LinkedList) Reverse() {
	p := l.head
	next := p.next
	p.next = nil
	for next != nil {
		tmp := next.next
		next.next = p
		p = next
		next = tmp
	}
	l.head, l.tail = l.tail, l.head
}

删除链表中间节点 (fast每次两步。slow每次一步，fast到头，slow刚好走一半)

//删除中间节点
func (l *LinkedList) DelMid() {
	fast := l.head
	slow := l.head
	prev := l.head
	for fast.next != nil && fast.next.next != nil {
		fast = fast.next.next
		prev = slow
		slow = slow.next
	}

	prev.next = slow.next
	if slow == l.head {
		l.head = slow.next
	}
}

删除链表倒数第K个节点 count = n + ( count - n)

// 删除链表的倒数第 K 个节点
// 使用快慢指针，快指针移动 K 个节点，然后慢指针再从头，
// 然后两个指针同时往后移动，快指针到结尾时，慢指针刚好到达倒数第 K 个节点，执行删除
func (l *LinkedList) DelLastKth(k int) {
	fast := l.head
	slow := l.head
	prev := l.head

	// 先移动 fast 指针 k 次
	for i := 0; i < k; i++ {
		fast = fast.next
	}

	// 移动 fast，slow 指针，把 fast 移动到最后
	for fast != nil {
		fast = fast.next
		prev = slow
		slow = slow.next
	}

	// 删除
	prev.next = slow.next
	if slow == l.head {
		l.head = slow.next
	}
}

特定节点后插入

链表环检测

有序链表合并

根据值寻找节点, 0(n)

根据index查找节点

在头部插入新节点

更新时间: