1. function LinkedList () {
    2.            //Node类表示要加入列表的项
    3.            var Node = function (element) {
    4.                this.element = element;;//要添加到链表的值
    5.                this.next = null;//指向链表中下一个节点项的指针
    6.            };
    8.            var length = 0;//链表项的数量
    9.            var head = null;//存储第一个节点的引用
    11.            //向链表尾部追加元素
    12.            this.append = function (element) {
    13.                 var node = new Node(element),   //创建Node项
    14.                     current;
    16.                 if (head === null) {//若head元素为null，意味着向链表添加第一个元素
    17.                     head = node;
    18.                 } else {
    19.                     current = head; //查询链表中的元素，需要从起点开始迭代
    20.                     while (current.next) {  
    21.                     //当current.next元素为null时，就知道已经到达链表的尾部了
    22.                         current = current.next;
    23.                     }
    24.                     current.next = node;
    25.                 }
    26.             length++;
    27.            };
    29.            //从链表中移除元素
    30.           this.removeAt = function (position) {
    31.               if (position > -1 && position < length) { //验证位置有效
    32.                  var current = head,   //用current变量创建链表中第一个元素引用
    33.                     previous, index = 0;
    34.                  if (position === 0) {
    35.                     head = cuttent.next;  //如果想要移除第一个，就让head指向第二个元素
    36.                  } else {
    37.                     while (index++ < position) {//迭代直到到达目标位置
    38.                         previous = current;
    39.                         current = current.next;
    40.                     }
    41.                     //将previous与current的下一项链接起来：跳过current，从而移除它
    42.                     previous.next = current.next;  
    43.                  }
    44.                  length--;
    45.                  return current.element;
    46.               } else {
    47.                   return null;
    48.               }   
    49.           };
    51.           //在任意位置插入一个元素
    52.           this.insert = function (positon, element) {
    53.               if (position >= 0 && position <= length) {//检查是否越界
    54.                    var node = new Node(element);
    55.                    var index = 0, previous, current = head;
    56.                    if (position === 0) {//在第一个位置添加
    57.                         node.next = current;
    58.                         head = node;
    59.                    } else {
    60.                         while (index++ < position) {
    61.                             previous = current;
    62.                             current = current.next;
    63.                         }
    64.                         node.next = current;
    65.                         previous.next = node;
    66.                    }
    67.                    length++;//更新链表长度
    68.                    return true;
    69.               } else {  
    70.                   return false;//如果越界返回false
    71.               }
    72.           }; 
    74.           //把LinkedList对象转换成一个字符串
    75.           this.toString = function () {
    76.               var current = head, //起点
    77.                   string = '';
    78.               while (current) {//检查元素是否存在
    79.                   string += ', ' + current.element;//拼接到字符串
    80.                   current = current.next;     
    81.               }
    82.               return string.slice(1);
    83.           };
    85.           //indexOf方法
    86.           this.indexOf = function (element) {
    87.               var current = head,
    88.                   index = 0;//计算位置数
    89.               while (current) {//循环访问元素
    90.                  if (element === current.element) {//检查当前元素是否是我们要找的
    91.                     return index;
    92.                  }
    93.                  index++;
    94.                  current = current.next;
    95.               }   
    96.               return -1;
    97.           };
    99.           //实现了indexOf方法后可以根据元素的值来移除元素
    100.           this.remove = function (element) {
    101.               var index = this.indexOf(element);
    102.               return this.removeAt(element);
    103.           };
    105.           //isEmpty方法和size方法与栈和队列中实现一样
    106.           this.isEmpty = function () {
    107.               return length === 0;//如果列表中没有元素，isEmpty方法就返回true，否则返回false
    108.           };
    109.           this.size = function () {
    110.               return length;
    111.           };
    113.           /**
    114.            *head变量是LinkedList类的私有变量
    115.            *意味着它不能在LinkedList实例外部访问和更改，只有通过LinkedList实例才可以
    116.            */
    117.           this.getHead = function () {
    118.               return head;
    119.           };
    120.        }
    1. function doubleLinkedList () {
    2.             var Node = function (element) {
    3.                 this.element = element;
    4.                 this.next = null;
    5.                 this.prev = null;//新增的，保存链表最后一项
    6.             };
    8.             var length = 0;
    9.             var head = null;
    10.             var tail = null;
    12.             //在任意一个位置插入一个新元素
    13.             this.insert = function (position, element) {
    14.                 //检查是否越界
    15.                 if (position >= 0 && position <= length) {
    16.                     var node = new Node(element),
    17.                         current = head,
    18.                         previous,
    19.                         index = 0;
    20.                     if (position === 0) {
    21.                         if (!head) {//如果链表为空，把head和tail都指向这个新节点
    22.                             head = node;
    23.                             tail = node;
    24.                         } else {
    25.                             node.next = current;
    26.                             current.prev = node;
    27.                             head = node;
    28.                         }
    29.                     } else if (position === length) {
    30.                         current = tail;
    31.                         current.next = node;
    32.                         node.prev = current;
    33.                         tail = node;
    34.                     } else {
    35.                         while (index++ < position) {
    36.                             previous = current;
    37.                             current = current.next;
    38.                         }
    39.                         node.next = current;
    40.                         previous.next = node;
    41.                         current.prev = node;
    42.                         node.prev = previous;
    43.                     }
    44.                     length++;
    45.                     return true;
    46.                 } else {
    47.                     return false;
    48.                 }
    49.             };
    51.             //从任意位置移除元素
    52.             this.removeAt = function (position) {
    53.                 if (position > -1 && position < length) {
    54.                     var current = head;
    55.                     previous, index = 0;
    57.                     if (position === 0) {//移除第一项
    58.                         head = current.next;
    59.                         if(length === 1) {//如果只有一项
    60.                             tail = null;
    61.                         } else {
    62.                             head.prev = null;//更新指向上一个元素的指针
    63.                         }
    64.                     } else if (position === length - 1) {//移除最后一项
    65.                         current = tail;
    66.                         tail = current.prev;
    67.                         tail.next = null;
    68.                     } else {
    69.                         while (index++ < position) {
    70.                             previous = current;
    71.                             current = current.next;
    72.                         }
    73.                         //将previous与current的下一项链接起来，跳过currrent
    74.                         previous.next = current.next;
    75.                         current.next.prev = previous;
    76.                     }
    77.                     length--;
    78.                     return current.element;
    79.                 } else {
    80.                     return null;
    81.                 }
    82.             };
    83.         }

    链表的实例

    1. /*JS实现一个基于对象的链表*/
    2. function Node(element){
    3.   this.element = element;//节点存储的元素
    4.   this.next = null;//节点指向的下一个节点，这里先设置为空
    5. }
    6. function LList(){
    7.   this.head = new Node("head");//生成一个头节点
    8.   this.find = find;//在链表中找到某个节点
    9.   this.insert = insert;//在链表中某个元素后面插入某个节点元素
    10.   this.display = display;//在将链表中的节点元素显示出来
    11.   this.findPrevious = findPrevious;//找到某个节点的上一个节点
    12.   this.remove = remove;//删除某个节点
    13. }
    14. function remove(item) {
    15.   var prevNode = this.findPrevious(item);
    16.   if (!(prevNode.next == null)) {
    17.     prevNode.next = prevNode.next.next;
    18.   }
    19. }
    20. function findPrevious(item) {
    21.   var currNode = this.head;
    22.   while (!(currNode.next == null) &&
    23.     (currNode.next.element != item)) {
    24.     currNode = currNode.next;
    25.   }
    26.   return currNode;
    27. }
    28. function display() {
    29.   var currNode = this.head;
    30.   var nodestr = "";
    31.   while (!(currNode.next == null)) {
    32.     nodestr +=" "+currNode.next.element;
    33.     currNode = currNode.next;
    34.   }
    35.   console.log(nodestr);
    36. }
    37. function find(item) {
    38.   var currNode = this.head;
    39.   while (currNode.element != item) {
    40.     currNode = currNode.next;
    41.   }
    42.   return currNode;
    43. }
    44. function insert(newElement, item) {
    45.   var newNode = new Node(newElement);
    46.   var current = this.find(item);
    47.   newNode.next = current.next;
    48.   current.next = newNode;
    49. }
    50. /*测试例子*/
    51. var num = new LList();
    52. num.insert("a1","head");
    53. num.insert("b1","a1");
    54. num.insert("c1","b1");
    55. num.display();// a1 b1 c1
    56. num.remove("b1");
    57. num.display();// a1 c1