JavaScript数据结构实现链表

链表存储元素的有序集合结构链表，但是与数组不同，链表中的元素不会连续放置在内存中. 每个元素都包含一个节点，该节点存储元素本身以及对下一个元素的引用（指针）.

链接列表的优点在于结构链表，添加或删除元素时无需移动其他元素. 链接列表的另一个细节是，您可以直接访问任何位置的任何元素. 如果要访问链接列表中间的元素，则需要从起点（列表标题）迭代链接列表，直到找到所需的元素.

LinkedList类具有以下方法:

追加（元素）: 在链接列表的末尾添加一个新项；

removeAt（位置）: 从链接列表中的特定位置删除项目；

插入（位置，元素）: 将新项目插入到链表中的特定位置；

indexOf（element）: 返回链表中元素的索引；如果元素不在链表中，则返回-1；

删除（元素）: 从链接列表中删除一项；

isEmpty（）: 如果链表不包含任何元素，则返回true；如果链表长度大于0，则返回false；

size（）: 返回链表中包含的元素数，类似于数组的length属性；

toString（）: 由于列表中使用了Node类，因此您需要覆盖从JavaScript对象继承的默认toStringfang方法，并仅让其输出元素值

function LinkedList () {
           //Node类表示要加入列表的项
           var Node = function (element) {
               this.element = element;;//要添加到链表的值
               this.next = null;//指向链表中下一个节点项的指针
           };
           var length = 0;//链表项的数量
           var head = null;//存储第一个节点的引用
           //向链表尾部追加元素
           this.append = function (element) {
                var node = new Node(element),   //创建Node项
                    current;
                if (head === null) {//若head元素为null，意味着向链表添加第一个元素
                    head = node;
                } else {
                    current = head; //查询链表中的元素，需要从起点开始迭代
                    while (current.next) {  
                    //当current.next元素为null时，就知道已经到达链表的尾部了
                        current = current.next;
                    }
                    current.next = node;
                }
            length++;
           };
           //从链表中移除元素
          this.removeAt = function (position) {
              if (position > -1 && position < length) { //验证位置有效
                 var current = head,   //用current变量创建链表中第一个元素引用
                    previous, index = 0;
                 if (position === 0) {
                    head = cuttent.next;  //如果想要移除第一个，就让head指向第二个元素
                 } else {
                    while (index++ < position) {//迭代直到到达目标位置
                        previous = current;
                        current = current.next;
                    }
                    //将previous与current的下一项链接起来：跳过current，从而移除它
                    previous.next = current.next;  
                 }
                 length--;
                 return current.element;
              } else {
                  return null;
              }   
          };
          //在任意位置插入一个元素
          this.insert = function (positon, element) {
              if (position >= 0 && position <= length) {//检查是否越界
                   var node = new Node(element);
                   var index = 0, previous, current = head;
                   if (position === 0) {//在第一个位置添加
                        node.next = current;
                        head = node;
                   } else {
                        while (index++ < position) {
                            previous = current;
                            current = current.next;
                        }
                        node.next = current;
                        previous.next = node;
                   }
                   length++;//更新链表长度
                   return true;
              } else {  
                  return false;//如果越界返回false
              }
          }; 
          //把LinkedList对象转换成一个字符串
          this.toString = function () {
              var current = head, //起点
                  string = '';
              while (current) {//检查元素是否存在
                  string += ', ' + current.element;//拼接到字符串
                  current = current.next;     
              }
              return string.slice(1);
          };
          //indexOf方法
          this.indexOf = function (element) {
              var current = head,
                  index = 0;//计算位置数
              while (current) {//循环访问元素
                 if (element === current.element) {//检查当前元素是否是我们要找的
                    return index;
                 }
                 index++;
                 current = current.next;
              }   
              return -1;
          };
          //实现了indexOf方法后可以根据元素的值来移除元素
          this.remove = function (element) {
              var index = this.indexOf(element);
              return this.removeAt(element);
          };
          //isEmpty方法和size方法与栈和队列中实现一样
          this.isEmpty = function () {
              return length === 0;//如果列表中没有元素，isEmpty方法就返回true，否则返回false
          };
          this.size = function () {
              return length;
          };
          /**
           *head变量是LinkedList类的私有变量
           *意味着它不能在LinkedList实例外部访问和更改，只有通过LinkedList实例才可以
           */
          this.getHead = function () {
              return head;
          };
       }

有许多不同类型的链表. 双链表和普通链表的区别在于: 在普通链表中，一个节点只有一个指向下一个节点的链接；在双向链表中，该链接是双向的: 一个链接指向下一个元素，另一个链接转发一个元素.

双向链表提供了两种迭代链表的方法: 从头到尾，反之亦然. 您可以访问特定节点的下一个或上一个元素. 如果错过了单向链表中要查找的元素，则需要返回到链表的开头并重新开始迭代. 这是双向链接列表的优点.

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