数据结构-链表

  |  

单向链表

js中数组的主要问题,js中的数组被实现成了对象,与其他语言的数组相比,效率很低

如果发现数组在实际使用时很慢,可以考虑使用链表来代替。当然,如果需要随机访问,数组仍然时更好的选择

因此,我们将使用js对象来描述链表

链表特点:

  1. 一个数据一个节点
  2. 节点特征 包含两部分, 一、element(值), 二、next(下一值的地址)
  3. 列表的增删节点等方法

链表

根据上面的特征,把链表描述,分为两个类实现

节点类 Node 用于描述节点
链表类 LList 用于方法实现

function Node(element){
this.element = element;
this.next = null;
}
function LList(){
this.head = new Node("head"); // 头节点
this.find = find;
this.findPrevious = findPrevious;
this.insert = insert;
this.insertHead = insertHead;
this.remove = remove;
this.display = display;
}
/*
最终,在js中展示的一个对象
head: {
element: xxx,
next:{
element: ...,
next: {...}
}
}
*/
// 链表的查询
function find(item){
let currentNode = this.head;
while(currentNode.element != item){
currentNode = currentNode.next;
}
return currentNode;
}
// 查找前一个节点
function findPrevious(item){
let currentNode = this.head;
// 只要不为空,以及下一节点的值不等于item,那么就一直查找
while(!(currentNode.next == null) && currentNode.next.element != item){
currentNode = currentNode.next;
}
return currentNode;
}
// 插入节点(在某个节点后插入,如果指定值不存在,则在尾部插入)
function insert(newItem,item){
let newNode = new Node(newItem);
let currentNode = this.find(item);
newNode.next = current.next;
current.next = newNode;
}
// 头插法
function insertHead(item){
let newNode = new Node(item);
newNode.next = this.head.next;
this.head.next = newNode;
}

// 删除节点
function remove(item){
let prev = this.findPrevious(item);
if(prev && !(prev.next == null)){
// 将前一个节点的next指向下两个
prev.next = prev.next.next;
return true
}
return false;
}
// 展示链表
function display(){
let currentNode = this.head;
// 只要数据为null,那么就不展示(因此,头节点肯定是不展示的)
while(!(currentNode.next === null)){
console.log(currentNode.element);
currentNode = currentNode.next;
}
}

添加一些辅助方法,比如advance(n) 向前移动n个节点,back(n) 向后移动n个节点,show() 显示当前节点

添加链表当前节点属性

function Llist(){
this.head = new Node('head');
this.current = this.head;
...
...
this.advance = advance;
this.back = back;
this.show = show;
}
function advance(n){
while(n > 0 && !(this.current.next == null)){
this.current = this.current.next;
n--
}
}
// 在双向链表中,才有前置指针previous
function back(n){
while(n>0 && !(this.current.element === 'head')){
this.current = this.current.previous
}
}
function show(){
console.log((this.current.element))
}

反转单向链表

利用递归的思维

function reverse( p =this.head) {
if(p.next) {
this.reverse(p.next)
}
}

双向链表

从 1 链表中,可见从链表的头节点遍历到尾节点很简单,只需要通过后向指针驱动 next 即可

但是,反过来,从后面向前遍历则没那么简单了,因此我们给节点添加前驱节点,那么即可往前遍历

双向链表

function Node(element){
this.element = element;
this.next = null; // 后驱
this.previous = null; // 前驱
}
function LList(){
this.head = new Node("head"); // 头节点
this.find = find;
this.findLast = findLast; // 拿到链表最后一个节点
// this.findPrevious = findPrevious; // 因为添加了前驱,所以查找前一个节点这个方法不必要了
this.insert = insert;
this.insertHead = insertHead;
this.remove = remove;
this.display = display;
this.reDisplay reDisplay; // 反转展示链表
}
function find(item){
let currentNode = this.head;
while(currentNode.element !== item){ // 只要没找到就一直next去寻找
currentNode = currentNode.next;
}
return currentNode;
}
function findLast(){
let currentNode = this.head;
while(!(currentNode.next == null)){
currentNode = currentNode.next;
}
return currentNode;
}
function insert(newItem,item){
let newNode = new Node(newItem);
let currentNode = this.find(item);
newNode.next = currentNode.next;
if(current.next){ // 如果只有头节点,那么不用前置previous
currentNode.next.previous = newNode;
}
newNode.previous = currentNode;
currentNode.next = newNode;
}
function remove(item){
let currentNode = this.find(item);
currentNode.previous.next = currentNode.next;
if(currentNode.next){ // 如果是尾节点才需要重置previous
currentNode.next.previous = currentNode.previous;
}
currentNode.next = null;
currentNode.previous = null;
}
function display(){
let currentNode=this.head;
while(!(currentNode.next==null)){
console.log(currentNode.next.element);
currentNode=currentNode.next;
}
}
function reDisplay() {
let currentNode = this.head;
currentNode = this.findLast();
while (!(currentNode.previous == null)) {
console.log(currentNode.element);
currentNode = currentNode.previous;
}
}

循环链表

循环链表与单向链表相似,节点类型都是一样的,唯一区别在于,在创建循环链表时,其头节点指向自身
循环链表

head.next = head;
function Node(element){
this.element = element;
this.next = null;
}
function LList(){
this.head = new Node('head');
this.head.next = this.head;
this.find = find;
this.findPrevious = findPrevious;
this.insert = insert;
this.display = display;
this.remove = remove;
}
// 循环链表中,与循环遍历相关的判断条件需要改变
function display(){
let currentNode = this.head;
while(!(currentNode.next == null) && !(currentNode.next.element == 'head')){
console.log(currentNode.next.element);
currentNode = currentNode.next;
}
}

面试常问


// 通过快慢指针的方式
function isAround(head) {
let fast = head;
let slow = head;
while(fast && fast.next) {
fast = fast.next.next;
slow = slow.next;
if(fast === slow) {
// 如果快慢指针相遇,那么代表存在环
return true
}
}
return false
}

// 找到链表环的起点位置
function startOfArround(head) {
let fast = head;
let slow = head;
while(fast && fast.next) {
fast = fast.next.next;
slow = slow.next;
if(fast === slow) {
// 如果快慢指针相遇,那么代表存在环
// return true
// 此时,需要寻找到环开始点,就变成了数学的追赶问题
// 假设 链表 3 > 2 > 0 > 4 > 2 (即4回到2)
// 假设 3 - 2 的距离为 a, 相遇点为4, 2-4距离为 b, 4-2距离为c
// fast的距离 为 a + n(b + c) + b , 其中n 为环的圈数, 因为环小的话,那么fast可能跑了好几圈了
// slow的距离为 a + b, 为什么没有 n ,因为就算最大环(即4-3,fast也就跑一圈就相遇了,因为fast = 2slow)
// 因此, a+(n+1)b+nc=2(a+b) ⟹ a=c+(n−1)(b+c)
// 由公式可以看出,从两指针相遇点到入环点的距离加上 n−1 圈的环长,恰好等于从链表头部到入环点的距离。
// 因此,当fast与slow相遇时,额外使用一个指针从head开始走,当head与slow指针相遇时,该位置就是环的起点。

fast = head; // 快指针从头开始, 即 从3开始
while(fast !== slow) {
fast = fast.next;
slow = slow.next;
}
return slow
}
}
return null
}

×

纯属好玩

扫码支持
扫码打赏,你说多少就多少

打开支付宝扫一扫,即可进行扫码打赏哦

文章目录
  1. 1. 单向链表
    1. 1.1. 反转单向链表
  2. 2. 双向链表
  3. 3. 循环链表
  4. 4. 面试常问
,