关于前端:数据结构学习链表

9次阅读

共计 656 个字符，预计需要花费 2 分钟才能阅读完成。

链表是 N 个数据元素的无限序列，最罕用的是链式表白，也叫线性链表或链表
链表中存储的数据元素也叫节点，一个节点存储的就是一条记录
每个结点的构造包含数据域、指针域两局部

单向链表 只能通过上一结点的指针找到下一个结点
循环链表 让单向链表最初一个元素的指针指向第一个元素
双向链 除了有指向下一个结点的指针外，再减少一个指向上一个结点的指针
双向循环链表 同时具备循环链表和双向链表交融的特色

一：操作系统内的动态内存调配
二：LRU 缓存淘汰算法

// 1. 链表插入
s.next = p.next
p.next = s

// 2. 链表删除
p.next = p.next.next

// 3. 链表反转
while(curr){
    next = curr.next
    curr.next = prev
    prev = curr
    curr = next
}
// 4  快慢指针
// 4.1 奇数个元素链表，快慢指针查问两头结点
while(fast && fast.next && fast.next.next){
    fast = fast.next.next;
    slow = slow.next;
}
// 4.2 快慢指还能够用来判断链表是否有环，如果链表存在环，快指针和慢指针肯定会在环内相遇，即 fast == slow 的状况肯定会产生

// 5. 虚构头：链表头可能产生扭转时可应用