乐趣区

关于数据结构:如何设计一个基于对象的链表

作者：

jiezi

在

前言

数据结构，应该大家或多或少都晓得，作为一个前端用的最多的数据结构就是数组了；在写业务中必然离不开数组，因为它岂但存储不便，操作还不便。在不思考效率的状况在，存储数据数组是集体的不二抉择。但数据结构还有一个叫“链表”的货色，“链表”在前端可能用的比拟少，反正作为底层人员，拿命换钱的我，工作了两年多还没用过“链表”，平时都是用数组，尽管可能用不到，但也无妨我学习。“链表”绝对于数组的增，删还是有劣势的，尽管查问比拟“拉胯”。古人云：“择其善者而从之”。

链表

单向链表是最一般的链表构造了，它是由多个节点组成相似链装的数据结构，样子大略如下：

链表会有一个非凡的节点叫“head”,它寄存第一个节点。每个节点会蕴含一个元素和一个指向下一个元素的“指针（next）”;最初一个节点的next会指向“空（null,undefind）”。

在js中，尽管有“链表”概念，然而它却没有提供内置创立“链表”的构造函数，不像一些后端语言有内置的构造函数。那么在js中，想要用“链表”存储数据，只能本人手动实现一些构造函数和办法。

设计一个链表它应该蕴含以下这些货色：

  • 链表构造函数
  • 节点构造函数
  • push办法（增加一个节点到链表最初）
  • insert办法 （增加一个元素到指定的地位）
  • removeAt办法 （删除一个指定地位的节点）
  • removeItem办法（删除一个指定元素的节点）
  • getElementAt办法 (获取一个指定地位的节点)
  • indexOf办法（获取一个元素的节点地位）
  • show办法 （展现所有链表数据）
  • size办法 （链表节点个数）
  • getHead办法 (获取头节点)
  • isEmpty办法 （判断列表是否为空）
  • 可能还有其余的，临时没想到

需要弄明确了，接下来就一步一步的实现一个链表构造。(为了不便了解，不会对代码进行封装，尽管有比拟多相似代码)

节点构造函数

一个一般的节点，只须要一个元素（element）和 一个指针（next）就行，无需其余多余的货色。

class Node {
  constructor(elememt){
    this.elememt = elememt
    this.next = undefined
  }
}

链表构造函数

链表构造函数须要一个头节点（head）和保留节点个数的count和下面的那些办法。


class LinkedList {
  constructor(){
    this.count = 0
    this.head = new Node('head')
  }
}

创立好构造后，就能够实现操作链表的办法了，当初链表的样子如下：

push办法

实现该办法前，先通过一张图理解一下它的增加逻辑。

push办法是在链表最初增加一个节点，假如，咱们要增加一个“张三”，那么就要通过Node构造函数创立一个叫“张三”的节点，而后，找到该链表的最初一个节点，断开它next指向undefined的链接，并将它指向新节点（如上图）。

逻辑分明，那么实现起来就不费劲了。


push(ele){
  // 创立新节点
  let newEle = new Node(ele)
  let current = this.head
  // 找到最初的那个节点
  while(current.next !== undefined){
    current = current.next
  }
  // 扭转最初一个节点的指针指向
  current.next = newEle
  // 节点个数加1
  this.count++
}

insert办法

假如，咱们要在第一个（index=0）的地位增加一个叫”李四”的节点，那么咱们就要找index的前一个节点，那么如上图，index的前一个节点就是head,咱们要找到它并将它的next指针指向新节点，还要将新元素的指针指向index节点。


insert(ele, index){
    // 越标解决
    if(index>=0 && index <= this.count){
      // 创立新元素
      let node = new Node(ele)
      let current=this.head , pre
      
      for (let i = 0; i <= index; i++) {
          // 保留 index 的前一个节点
        pre = current
        // index的指标节点
        current =current.next
      }
      // index 的前一个节点的指针指向新节点
      pre.next = node
      // 新节点指针指向index的指标节点
      node.next = current
      // 节点加1
      this.count++
    }else{
      console.error('越标')
    }
  }

removeAt办法

假如，咱们要删除第一项（index === 0）,那么就要找到它（index=0）的前一个节点，并将它的指针指向index=0下一个节点，也就是它的next,最初将删除的节点指针重置为undefined。


 removeAt(index){
     // 越标解决
    if(index >= 0 && index < this.count){
      let current=this.head , pre
      for (let i = 0; i <= index; i++) {
          // index前一项
        pre = current
        // index项
        current =current.next
      }
      // 扭转index前一项指针指向，让它跳过index项，指向到index下一项
      pre.next = current.next
      current.next = undefined
      // 节点减一
      this.count--
    }else{
      console.error('删除失败，越标')
    }
  }

removeItem办法

这办法是通过元素删除，逻辑跟下面差不多，就不上图了。


removeItem(ele){
  let current = this.head,pre
  try {
    while(current.elememt !== ele){
      pre = current
      current = current.next
    }
  } catch (error) {
    console.error('删除失败，没有该元素')
  }
  pre.next = current.next
  this.count--
}

getElementAt办法

该办法次要是通过index找到对应的节点,找到就返回该节点，没找到就返回undefined。


 getElement(index){
    if(index >= 0 && index < this.count){
      let node = this.head
      for (let i = 0; i <= index; i++) {
        node = node.next        
      }
      return node
    }
    return undefined
  }

indexOf办法

该办法次要是通过元素找到下标,找到就返回下标，没找到就返回-1。


indexOf(ele){
  let current = this.head
  for (let i = 0; i < this.count; i++) {
    if(ele === current.elememt){
      return i
    }
    current = current.next
  }
  return -1
}

size、getHead、isEmpty、show办法

size办法获取节点的个数，getHead办法获取链表的头节点，isEmpty办法判断链表是否为空，show办法展现链表元素。


 size(){
    return this.count
  }

  getHead(){
    return this.head
  }

  isEmpty(){
    return this.count === 0
  }

  show(){
    if(this.count > 0){
      let current = this.head
      while(current.next !== undefined){
          // 这里只是做了打印展现
        console.log(current.next.elememt)
        current = current.next
      }
    }
  }

测试


  let personLink = new LinkedList()
  
  personLink.push('张三')
  
  personLink.push('李四')
  
  personLink.insert('王五', 1)
  
  personLink.removeAt(1)
  
  console.log(personLink.getHead())
  
  personLink.show()
  
  personLink.removeAt(1)
  
  console.log(personLink.indexOf('王五'))

残缺代码


class Node {
  constructor(elememt){
    this.elememt = elememt
    this.next = undefined
  }
}

class LinkedList {
  constructor(){
    this.count = 0
    this.head = new Node('head')
  }

  push(ele){
    let newEle = new Node(ele)
    let current = this.head
    while(current.next !== undefined){
      current = current.next
    }
    current.next = newEle
    this.count++
  }
 
  size(){
    return this.count
  }

  getHead(){
    return this.head
  }

  isEmpty(){
    return this.count === 0
  }

  show(){
    if(this.count > 0){
      let current = this.head
      while(current.next !== undefined){
        console.log(current.next.elememt)
        current = current.next
      }
    }
  }

  removeAt(index){
    if(index >= 0 && index < this.count){
      let current=this.head , pre
      for (let i = 0; i <= index; i++) {
        pre = current
        current =current.next
      }
      pre.next = current.next
      current.next = undefined
      this.count--
    }else{
      console.error('删除失败，越标')
    }
  }

  removeItem(ele){
    let current = this.head,pre
    try {
      while(current.elememt !== ele){
        pre = current
        current = current.next
      }
    } catch (error) {
      console.error('删除失败，没有该元素')
    }
    pre.next = current.next
    this.count--
  }

  getElement(index){
    if(index >= 0 && index < this.count){
      let node = this.head
      for (let i = 0; i <= index; i++) {
        node = node.next        
      }
      return node
    }
    return undefined
  }

  insert(ele, index){
    if(index>=0 && index <= this.count){
      let node = new Node(ele)
      let current=this.head , pre
      for (let i = 0; i <= index; i++) {
        pre = current
        current =current.next
      }
      pre.next = node
      node.next = current
      this.count++
    }else{
      console.error('越标')
    }
  }

  indexOf(ele){
    let current = this.head
    for (let i = 0; i < this.count; i++) {
      if(ele === current.elememt){
        return i
      }
      current = current.next
    }
    return -1
  }

}

let personLink = new LinkedList()
personLink.push('张三')
personLink.push('李四')
personLink.insert('王五', 1)
personLink.removeAt(1)
console.log(personLink.getHead())
personLink.show()
personLink.removeAt(1)
console.log(personLink.indexOf('王五'))

评论

发表回复

您的邮箱地址不会被公开。 必填项已用 * 标注

这个站点使用 Akismet 来减少垃圾评论。了解你的评论数据如何被处理。

更多文章