JS实现数据结构（四）：双向链表_js数据结构双链表

• 单向链表只能从从遍历到尾，缺点是可以轻松到达下一个节点，但是很难回到上一个节点
• 双向链表可以从头遍历到尾，也可以从尾遍历到头，一个节点既有向前的引用，也有向后的引用
• 双向链表结构- 双向链表方法
  • append（element）：向列表尾部添加一个新的项
  • insert（position，element）：向列表的特定位置插入一个新的项。
  • get（position）：获取对应位置的元素
  • indexOf（element）：返回元素在列表中的索引。如果列表中没有该元素则返回-1。
  • update（position，element）：修改某个位置的元素
  • removeAt（position）：从列表的特定位置移除一项。
  • remove（element）：从列表中移除一项。
  • isEmpty（）：如果链表中不包含任何元素，返回true，如果链表长度大于0则返回false.
  • size（）：返回链表包含的元素个数。与数组的length属性类似。
  • toString（）：由于列表项使用了Node类，就需要重写继承自JavaScript对象默认的toString方法，让其只输出元素的值。
  • forwardString（）：返回正向遍历的节点字符串形式
  • backwordString（）：返回反向遍历的节点字符串形式
• 封装双向链表

function DoubleLinkedList(){
   
  //内部类：节点类
  function Node(data){
   
    this.data = data;
    this.pre =  null;
    this.next = null;
  }
  //属性
  this.head = null;
  this.tail = null;
  this.length = 0 ;
  
  //1.append()
  DoubleLinkedList.prototype.append = function(data){
   
    var newNode = new Node(data);
    
    if(this.length === 0){
   
      this.head = newNode;
      this.tail = newNode;
    }else{
   
      newNode.pre = this.tail;
      this.tail.next = newNode;
      this.tail = newNode;
    }
    this.length += 1;
  }
  
  //2.insert()
  DoubleLinkedList.prototype.insert = function(position，data){
   
    //越界判断
    if(position < 0 || position > this.lengh) return false
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36