单向链表

  • 新增 append(elem) 链表尾部添加新项
  • 插入 insert(elem,position) 在特定的位置插入元素
  • 移除 removeAt 重列表中特定的位置移除
  • isEmpty 判断链表是否为空
  • indexOf(elem) 返回元素在列表中的位置
  • size 返回链表长度
  • toString 返回所有链表元素的拼接字符串
  1. function LinkedList(){
  2.     // 链表实现
  3.     var length = 0; // 链表元素个数
  4.     var head = null; // 链表开头元素
  6.         // 链表单元类
  7.     function Node(elem){
  8.         this.elem = elem;
  9.         this.next = null;
  10.     }
  12.     /** 
  13.      * @function append 添加元素
  14.      * @argument {elem} 
  15.      * @returns
  16.      */
  17.     this.append = function(elem){
  18.         var node = new Node(elem);
  19.         var current; // 链表的当前一个
  20.         // 如果链表中没有其他元素
  21.         if(!head){
  22.             head = node;
  23.         }else{
  24.             // 遍历链表 添加到最后一个
  25.              current = head;
  26.             while(current.next){ // 重第一个开始遍历找到最后一个再添加上
  27.                 current = current.next;
  28.             }
  29.             current.next = node;
  30.         }
  31.         // 更新链表长度
  32.         length =length+1;
  33.     }
  35.     /**
  36.      * @function moveAt 
  37.      * @argument {position} number
  38.      * @returns {any}
  39.      */
  40.     this.moveAt = function(position){
  41.         // 边界判断
  42.         if(position>-1&&position<length){
  43.             var current; // 当前元素
  44.             var pre; // 前一个元素
  45.             var index = 0; // 迭代指针
  46.             // 如果是第一个
  47.             if(position === 0){
  48.                 head = head.next;
  49.             }else{
  50.                 current = head;
  51.                 while(index < position){
  52.                     pre = current;
  53.                     current = current.next;
  54.                     index ++;
  55.                 }
  56.                 // 将前一个元素和后一个元素连接起来
  57.                 pre.next = current.next;
  58.             }
  59.             length --;
  60.             return current.elem;
  61.         }else{
  62.             return null;
  63.         }
  64.     }
  66.     /**
  67.      * @function insert
  68.      * @argument {elem,position}
  69.      * @returns {boolean}
  70.      */
  71.     this.insert = function(elem,position){
  72.         var node = new Node(elem);
  73.         var index = 0; // 迭代指针
  74.         var current = head; // 当前元素
  75.         var pre; // 前一个元素
  76.         // 边界判断
  77.         if(position>-1&&position<length){
  78.             // 当插入的位置是0
  79.             if(position === 0){
  80.                 node.next = current;
  81.             }else{
  82.                 while(index<position){
  83.                     pre = current;
  84.                     current = current.next;
  85.                     index ++;
  86.                 }
  87.                 node.next = current;
  88.                 pre.next = node;
  89.             };
  90.             // 更新长度
  91.             length ++;
  92.             return true;    
  93.         }else{
  94.             return false;
  95.         }
  96.     }
  97.     /**
  98.      * @function toString
  99.      * @returns {string}
  100.      */
  101.     this.toString = function(){
  102.         var current = head;
  103.         var str = '';
  104.         while(current){
  105.             str += `${current.elem} `;
  106.             current = current.next;
  107.         }
  108.         return str;
  109.     }
  110.     /**
  111.      * @function indexOf
  112.      * @argument {elem}
  113.      * @returns {number}
  114.      */
  115.     this.indexOf = function(elem){
  116.         var index = 0; // 迭代指针
  117.         var current = head;
  118.         while(current){
  119.             if(current.elem === elem){
  120.                 return index;
  121.             }
  122.             index ++;
  123.             current = current.next;
  124.         }
  125.         return -1;
  126.     }
  128.     /**
  129.      * @function isEmpty
  130.      * @returns {boolean}
  131.      */
  132.     this.isEmpty = function(){
  133.         return length === 0;
  134.     }
  136.     /**
  137.      * @function size
  138.      * @returns {number}
  139.      */
  140.     this.size = function(){
  141.         return length;
  142.     }
  144.     /**
  145.      * @function getHead
  146.      * @returns {object}
  147.      */
  148.     this.getHead = function(){
  149.         return head;
  150.     }
  151. }
  153. var linklist = new LinkedList();
  154. linklist.append(1);
  155. linklist.append(2);
  156. linklist.append(3);
  157. linklist.append(4);
  158. // console.log(linklist.getHead())
  159. linklist.insert(31,2);
  160. console.log(linklist.toString())
  161. console.log(linklist.size())
  162. console.log(linklist.isEmpty())
  163. console.log(linklist.moveAt(2))