JavaScript数据结构之链表的实现

既然栈方法都实现了，先入先出的队列怎么能少，shift方法可以删除数组index最小元素，并使后面元素index都减一，length也减一，这样使用shift/push就可以模拟队列了，当然与shift方法对应的有一个unshift方法，用于向数组头部添加一个元素。在前面我们分析了hashmap和linkedhashmap，在jdk 1.8 中 hashmap是数组+链表+红黑树实现的,当hash表某个位置上的元素个数超过某个阀值过后就采用红黑树结构，否则采用链表结构结构链表，在hashmap中元素 相对插入顺序是无序的，也就是说其遍历顺序不可预测。树形结构:元素之间存在一对多的关系,常见类型有:树(有许多特例:二叉树、平衡二叉树、查找树等)图形结构:元素之间存在多对多的关系,图形结构中每个结点的前驱结点数和后续结点多个数可以任意常用数据结构：数组（静态数组、动态数组）、线性表、链表（单向链表、双向链表、循环链表）、队列、栈、树（二叉树、查找树、平衡树、线索、堆）、图等的定义、存储和操作。

链表的概念

链表是一种常见的数据结构。它是动态地进行存储分配的一种结构。链表有一个“头指针”变量，以head表示，它存放一个地址，指向一个元素。每个结点都使用一个对象的引用指标它的后继，指向另一个结点的引用叫做链。

由于使用数组作为链表的存储空间，所以链表的元素肯定会分布在数组的一些元素上去，但是对于链表进行插入操作时，会出现链表的顺序和数组的下表顺序不一致的情况，可能会导致数组中的一些连续空间为空，即未被使用，可能是这里的元素之前被删除了。静态链表的尾插入类似，首先从备用链表头拿出一个元素，把备用链表的头标记指向备用链表的第2个元素的数组下标，因为要作为链表的最后一个元素，因此把这个元素的cur设为空，接着把真是链表的为指针指向这个数组元素cur设为这个被拿出来的元素的下标，接着把为指针标记的值设为这个元素的数组下标，这样就完成了链表的尾插入。（注意：在使用这个函数获得尾结点指针时，必须在每次插入结点元素后重新获得，因为链表尾部结点是会随着结点的插入而发生变化）。

删除过程：

基于对象的链表

定义函数node *create_llist_sorted()，用来创建非递减有序带头结点的单链表，定义四个指针node*h,*p,*q,*s，头指针指向第一个结点，并且分配空间给头指针h，使头指针不为空，*p指向单链表中某一结点，*q指向*p的前驱,*s指向输入的数据，将数据逐个输入，将输入的数据通过循环语句不断进行比较，其中先使*q指向*h所指位置，*p指向*h的下一个位置，不断将输入的每一个数据与链表中的数据相比较，找到插入位置，然后移动*p，*q，直到*p为空指针且*s所指数据小于等于*p所指数据，从而使数据有序，最后返回头指针。key 0基本操作： creatlist &phead,k 操作结果：构造单循环链表 printlist phead 初始条件：链表已存在 操作结果：打印输出链表数据元素 joesph &phead,m 初始条件：链表已存在，m为出列者所在编号 操作结果：删除出队编号所在结点，并将该结点的key作为新的key，从该结点的下一结点移动adt node存储结构定义数据存储结构的c语言定义如下：typedef struct node //带头结点的单循环链表int id。最近看了《剑指offer》这本书，遇到了一个问题：反转链表 题目:定义一个函数结构链表，输入一个链表的头结点，反转该链表并输出反转后的链表的头结点。

首先看Node类：

function Node(element){
  this.element = element;
   this.next = null;
 }

element用来保存结点上的数据，next用来保存指向一下结点的的链接。

LinkedList类:

function LinkedList(){
     this.head = new Node('head');
     this.find = find;
     this.insert = insert;
     this.remove = remove;
     this.show = show;
}

我总结的二分无非就4种情况：yes_left、yes_right、no_left、no_right，分别代表：能找到且返回最左边的数的位置（如查找4的时候返回位置3）、能找到且返回最右边的数的位置（如查找4的时候返回位置4）、不能找到且返回左边与其接近的数的位置（如查找3的时候返回位置2）、不能找到且返回右边与其接近的数的位置（如查找3的时候返回位置3）。这个函数的思路是通过头结点找到尾结点，首先判断链表是否为空，不为空时对链表进行遍历，返回下一个结点为空的上一个结点，该结点即使结点的尾部。定义函数node *del(node *h, int i)，用于删除单链表h中第i个结点，定义两个指针*p，*q，用指针p来从第一个结点开始查找需要删除的结点，指针q是指针p的前驱，查找过程中，不断移动指针p，q，直至找到需要删除的结点，如果*p为空指针，则表示链表中没有需要删除的结点，最后返回头指针。

function find(item){
     var currentNode = this.head;//从头结点开始
     while(currentNode.element!=item){
         currentNode = currentNode.next;
     }
     return currentNode;//找到返回结点数据，没找到返回null
}

Insert方法。通过前面元素插入的演示可以看出，实现插入简单四步：

1、创建结点

2、找到目标结点

3、修改目标结点的next指向链接

4、将目标结点的next值赋值给要插入的结点的next

function insert(newElement,item){
     var newNode = new Node(newElement);
     var currentNode = this.find(item);
     newNode.next = currentNode.next;
     currentNode.next = newNode;
 }

Remove()方法。删除某一节点需要先找到被删除结点的前结点，为此我们定义方法frontNode()：

function frontNode(item){
     var currentNode = this.head;
     while(currentNode.next.element!=item&&currentNode.next!=null){
         currentNode = currentNode.next;
     }   
     return currentNode;
}

简答三步：

1、创建结点

2、找到目标结点的前结点

3、修改前结点的next指向被删除结点的n后一个结点

function remove(item){
     var frontNode = this.frontNode(item);
     //console.log(frontNode.element);
     frontNode.next = frontNode.next.next;
 }

Show()方法：

function show(){
     var currentNode = this.head,result;
     while(currentNode.next!=null){
         result += currentNode.next.element;//为了不显示head结点
         currentNode = currentNode.next;
     }
}

测试程序：

var list = new LinkedList();
list.insert("a","head");
list.insert("b","a");
list.insert("c","b");
console.log(list.show());
list.remove("b");
console.log(list.show());

输出：

双向链表

从链表的头节点遍历到尾节点很简单，但有的时候，我们需要从后向前遍。此时我们可以通过给 Node 对象增加一个属性，该属性存储指向前驱节点的链接。楼主用下图来双向链表的工作原理。

首先我们先给Node类增加front属性：

function Node(element){
  this.element = element;
  this.next = null;
   this.front = null;
 }

当然，对应的insert()方法和remove()方法我们也需要做相应的修改：

function insert(newElement,item){
  var newNode = new Node(newElement);
  var currentNode = this.find(item);
  newNode.next = currentNode.next;
  newNode.front = currentNode;//增加front指向前驱结点
  currentNode.next = newNode;
}
function remove(item){  
  var currentNode = this.find(item);//找到需要删除的节点
  if (currentNode.next != null) {
    currentNode.front.next = currentNode.next;//让前驱节点指向需要删除的节点的下一个节点
    currentNode.next.front = currentNode.front;//让后继节点指向需要删除的节点的上一个节点
    currentNode.next = null;//并设置前驱与后继的指向为空
    currentNode.front = null;    
  }  
}

反序显示链表：

/*********name:locate_pre_valueinput_param:链表地址llist，节点p的地址output:return:节点p的前驱节点地址function:成功：查找p节点所指向节点的前驱节点。}}/*********name:locate_pre_valueinput_param:链表地址llist，节点p的地址output:return:节点p的前驱节点地址function:成功：查找p节点所指向节点的前驱节点。 p = p->next)//循环遍历链表中的节点，找出此时最小的节点。

function findLast() {//查找链表的最后一个节点
  var currentNode = this.head;
  while (currentNode.next != null) {
    currentNode = currentNode.next;
  }
  return currentNode;
}

实现反序输出：

function showReverse() {
  var currentNode = this.head, result = "";
  currentNode = this.findLast(); 
  while(currentNode.front!=null){
    result += currentNode.element + " ";
    currentNode = currentNode.front;
  }
  return result;
}

测试程序：

var list = new LinkedList();
list.insert("a","head");
list.insert("b","a");
list.insert("c","b");
console.log(list);
list.remove("b");
console.log(list.show());
console.log(list.showReverse());

输出：

循环链表

循环链表是另一种形式的链式存贮结构。它的特点是表中最后一个结点的指针域指向头结点，整个链表形成一个环。循环链表和单向链表相似，节点类型都是一样的。唯一的区别是，在创建循环链表时，让其头节点的 next 属性指向它本身，即：

head.next = head

这种行为会传导至链表中的每个节点，使得每个节点的 next 属性都指向链表的头节点。楼主用下图来表示循环链表：

修改构造方法：

function LinkedList(){
  this.head = new Node('head');//初始化
  this.head.next = this.head;//直接将头节点的next指向头节点形成循环链表
  this.find = find;
  this.frontNode = frontNode;
  this.insert = insert;
  this.remove = remove;
  this.show = show; 
}

这时需要注意链表的输出方法show()与find()方法，原来的方式在循环链表里会陷入死循环，while循环的循环条件需要修改为当循环到头节点时退出循环。

function find(item){
  var currentNode = this.head;//从头结点开始
  while(currentNode.element!=item&&currentNode.next.element!='head'){
    currentNode = currentNode.next;
  }
  return currentNode;//找到返回结点数据，没找到返回null
}
function show(){
  var currentNode = this.head,result = "";
  while (currentNode.next != null && currentNode.next.element != "head") {   
    result += currentNode.next.element + " ";
    currentNode = currentNode.next;
  }
  return result;
}

测试程序：

var list = new LinkedList();
list.insert("a","head");
list.insert("b","a");
list.insert("c","b");
console.log(list.show());
list.remove("b");
console.log(list.show());

测试结果：

本文用到的示例代码地址：

以上就是本文的全部内容，希望本文的内容对大家的学习或者工作能带来一定的帮助，同时也希望多多支持脚本之家！

本文来自电脑杂谈，转载请注明本文网址：
http://www.pc-fly.com/a/jisuanjixue/article-109125-1.html