欢迎光临
我的个人博客网站

前端数据结构–线性结构-链表


链表

  标准数组是一块连续的内存地址,所以在做插入、删除时会对数据进行大量的移动,如果数据量很大那么效率会比较低。如果我们把每一个元素都记录着下一个元素的地址,那我们在做插入、删除时是不是只需要改变下一个元素的地址即可, 如

前端数据结构--线性结构-链表

 从存储结构来看链表不需要一块连续的内存空间,它通过“指针”将一组零散的内存块串联起来使用 

前端数据结构--线性结构-链表

 常见的链表结构有单链表、双向链表、循环链表、双向循环链表。

单链表

  链表中的每一个节点都具备两个功能:一个功能是存储数据,另外一个功能是记录下一个节点的地址。当结点只记录下一个结点的地址且最后一个结点指向null,这种链表叫单链表。

前端数据结构--线性结构-链表

循环链表

  循环链表是一种特殊的单链表。它跟单链表的区别就在尾结点。单链表的尾结点指针指向null 空地址,表示这是最后的结点,而循环链表的尾结点指针是指向链表的头结点 如

前端数据结构--线性结构-链表

双向链表

  单链表只有一个方向,结点只有一个指向后面结点的指针,双向链表支持两个方向,一个是前面,一个是后面 如

前端数据结构--线性结构-链表

双向循环链表

  把循环链表、双向链表组合就是双向循环链表,结点可以指向前面、后面结点的指针,同时尾结点还指向了头结点 如

前端数据结构--线性结构-链表

 数组与链表

数组与链表是两种不同的内存组织方式,数组的特点是随机访问、内存地址连续,插入、删除操作不需要移动元素。链表结点要保存上一个结点、下一个结点的信息(对内存的消耗比较大),对于插入、删除操作只需要改变引用的指针即可。

 js 实现单链表

 1 /*  2   数据是1:1的关系  3   单向链表:只有指向一个方向  4   循环链表:末尾节点指向头部节点(跟节点)   5   双向链表:节点存在指向上、下节点的引用  6   双向循环链表:把循环链表、双向链表组合而成  7 */  8   9 class Node { 10   constructor (data) { 11     this.data = data 12     this.next = null 13   } 14 } 15  16 class linkedList  { 17   constructor () { 18     this.header = null 19     this.size = 0 20   } 21   // 插入末尾 22   append (data) { 23     const addNode = new Node(data) 24     if (!this.header) { 25       this.header = addNode 26     } else { 27       const currNode = this.find() 28       currNode.next = addNode 29     } 30     this.size++ 31   } 32   // 插入到x位置,其中是x索引从0开始 33   insertAt (index, data) { 34     if (index < 0 || index > this.size) { 35       throw new Error('插入的位置不正确') 36     } 37     const node = new Node(data) 38     if (index === 0) { 39       node.next = this.header 40       this.header = node 41     } else { 42       let pre = this.getNode(index - 1) 43       node.next = pre.next 44       pre.next = node 45     } 46     this.size++ 47   } 48   // 删除 49   remove (index) { 50     if (index < 0 || index >= this.size) { 51       throw new Error('超出链表索引') 52     } 53      54     if (index === 0) { 55       this.header = this.header.next 56     } else { 57       const pre = this.getNode(index - 1) 58       const delNode = pre.next 59       pre.next = delNode.next 60     } 61     this.size-- 62   } 63   // 通过索引获取 64   getNode (index) { 65     if (index < 0 || index >= this.size) { 66       throw new Error('超出链表索引') 67     } 68     let currentNode = this.header 69     for (let i = 0; i < index; i++) { 70       currentNode = currentNode.next 71     } 72     return currentNode 73   } 74   // 获取末尾节点 75   find () { 76     let currentNode = this.header 77     while (currentNode.next) { 78       currentNode = currentNode.next 79    } 80    return currentNode 81   } 82 } 83  84 const linkList = new linkedList() 85 linkList.append('header') 86 linkList.append(1) 87 linkList.append(2) 88 linkList.append(3) 89 linkList.insertAt(4, 4) 90 linkList.insertAt(3, '3-before') // 插入到3的前面 91  92 linkList.remove(4) 93 console.log(linkList)

对链表的插入、删除操作,在插入第一个结点和删除最后一个结点的情况,需要进行特殊处理,即空链。

预览 codepen

 

赞(0) 打赏
未经允许不得转载:张拓的天空 » 前端数据结构–线性结构-链表
分享到: 更多 (0)

评论 抢沙发

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址

专业的IT技术经验分享 更专业 更方便

联系我们本站主机

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

微信扫一扫打赏