链表

• 链表是物理存储上非连续的、非顺序的存储结构，由一系列结点构成。
• 无头链表是指第一个结点既有数据域，又有指针域，第一个结点既是首节点又是头节点
• 有头链表是指第一个节点只有指针域，而没有数据域

链表的方法

• append 添加一个新的元素
• insert 在指定位置插入一个元素
• remove 删除指定位置的结点
• remove_head 删除首节点
• remove_tail 删除尾结点
• indexOf 返回指定元素的索引
• get 返回指定索引位置的元素
• head 返回首节点
• tail 返回尾结点
• length 返回链表长度
• isEmpty 判断链表是否为空
• clear 清空链表
• print 打印整个链表

结点

• 结点包含两部分，一部分是存储数据的数据域，一部分是存储指向下一个结点的指针域。

var Node = function(data) {
  this.data = data
  this.next = null
}

链表的实现

• 定义链表类

function LinkList() {
  // 定义节点
  var Node = function(data) {
    this.data = data
    this.next = null
  }

  var length = 0        // 长度
  var head = null       // 头节点
  var tail = null       // 尾结点

  // 添加结点
  this.append = function(data) {
    // 创建节点
    var new_node = new Node(data)
    if(head == null) {
      head = new_node
      tail = new_node
    } else {
      tail.next = new_node
      tail = new_node
    }
    length += 1;
    return true
  }
  
  // 打印节点
  this.print = function() {
    var curr_node = head
    while(curr_node) {
      console.log(curr_node.data)
      curr_node = curr_node.next
    }
  }
  this.insert = function(index, data) {
    if(index < 0 && index > length) {
      return false
    } else if(index === length) {
      return this.append(data)
    } else {
      var new_node = new Node(data)
      // new_node变成新的头节点
      if(index == 0) {
        new_node.next = head
        head = new_node
      } else {
        var insert_index = 1
        var curr_node = head
        while(insert_index < index){
          insert_index += 1
          curr_node = curr_node.next
        }
        // 当循环结束的时候
        var next_node = curr_node.next
        curr_node.next = new_node
        new_node.next = next_node
      }
      length += 1
      return true
    }
  }

  // 移除节点
  this.remove = function(index) {
    if(index < 0 || index >= length) {
      return null
    } else {
      var del_node = null
      if(index == 0) {
        del_node = head
        head = head.next
      } else {
        var del_index = 0
        var pre_node = null     // 被删除节点的前一个节点
        var curr_node = head    // 要被删除的节点
        while(del_index < index) {
          del_index += 1
          pre_node = curr_node
          curr_node = curr_node.next
        } 

        del_node = curr_node
        // 被删除节点的前一个节点指向被删除节点的后一个节点
        pre_node.next = curr_node.next

        // 如果被删除的节点是尾结点
        if(curr_node.next == null) {
          tail = pre_node
        }
      }

      length -= 1
      del_node.next = null
      return del_node.data
    } 
  }

  //  返回指定位置节点的值
  this.get = function(index) {
    if(index < 0 || index >= length) {
      return null
    }

    var node_index = 0
    var curr_node = head
    while(node_index < index) {
      node_index += 1
      curr_node = curr_node.next
    }
    return curr_node.data
  }
}

• 翻转链表
  • 定义结点类

  var Node = function(data) {
    this.data = data
    this.next = null
  }
  
  var node1 = new Node(1)
  var node2 = new Node(2)
  var node3 = new Node(3)
  var node4 = new Node(4)
  var node5 = new Node(5)
  
  node1.next = node2
  node2.next = node3
  node3.next = node4
  node4.next = node5
  
  function print(node) {
    var curr_node = node
    while(curr_node) {
      console.log(curr_node.data)
      curr_node = curr_node.next
    }
  }
  

  • 迭代翻转

   function reverse_iter(head) {
     if(!head) {
       return null
     }
     var pre_node = null         // 前一个节点
     var curr_node = head        // 当前要翻转的节点
     while(curr_node) {
       var next_node = curr_node.next     // 下一个节点
       curr_node.next = pre_node          // 对当前节点进行翻转
       pre_node = curr_node               // pre_node 向后滑动
       curr_node = next_node              // curr_node 向后滑动
     }
     // 最后要返回 pre_node  当循环结束时, pre_node 指向翻转前链表的最后一个节点
     return pre_node
   }
  
    print(reverse_iter(node1))
  

  • 递归翻转

  function reverse_digui(head) {
    // 如果head 为null
    if(!head) {
      return null
    } 
    if(head.next == null) {
      return head
    }
  
    // 从下一个节点开始进行翻转
    var new_head = reverse_digui(head.next)
    head.next.next = head        // 把当前节点连接到新链表上
    head.next = null
    return new_head
  }
  print(reverse_digui(node1))