javascript实现数据结构：线性表--线性链表（链式存储结构）

浏览数：24 / 时间：2015年06月08日

上一节中，线性表的顺序存储结构的特点是逻辑关系上相邻的两个元素在物理位置上也相邻，因此可以随机存取表中任一元素，它的存储位置可用一个简单，直观的公式来表示。然后，另一方面来看，这个特点也造成这种存储结构的弱点，在做插入或删除操作时，需移动大量元素。

而链式存储结构，由于它不需要逻辑上相邻的元素在物理位置上也相邻，因此它没有顺序存储结构所具有的弱点，但同时也失去了顺序表可随机存取的优点。

线性链表

线性表的链式存储结构的特点是用一组任意的存储单元储存线性表的数据元素（这组存储单元可以是连续的，也可以是不连续的）。因此，为了表示每个数据元素a(i)与其直接后继数据元素a(i+1)之间的逻辑关系，对数据元素a(i)来说，除了存储其本身的信息之外，还需存储一个指示其直接后继的信息（即直接后继的存储位置）。这两部分信息组成数据元素a(i)的存储映像，称为结点（node）。它包括两个域：其中存储数据元素信息的域称为数据域；存储直接后继存储位置的域称为指针域，指针域中存储的信息称做指针或链。

又由于此链表的每个结点中只包含一个指针域，故又称线性链表或单链表。

单链表的整个链表的存取必须从头指针开始进行，头指针指示链表中第一个结点（即第一个数据元素的存储映像）的存储位置。

同时，由于最后一个数据元素没有直接后继，则线性链表中最后一个结点的指针为空null。

1 // 线性表的单链表存储结构
2 function LNode(data, node) {
3   this.data = data;
4   this.next = node || null;
5 }

假设p是指向线性表中第i个数据元素（结点a(i)）的指针，则p->next是指向第i+1个数据元素（结点a(i+1)）的指针。

下面我们来看GetElem在单链表中的实现：

 1 function getElem(i) {
 2     // 初始化，p指向第一个节点，j为计数器
 3     var p = this.next;
 4     var j = 1;
 5     // 顺指针向后查找，知道p指向第i个元素或p为空
 6     while (p && j < i) {
 7       p = p.next;
 8       ++j;
 9     }
10     // 第i个元素不存在
11     // 或者取第i个元素
12     return (!p || j > i) ? null : p.data;
13   }

单链表的基本操作：

假设我们在线性表的两个数据元素a和b之间插入一个数据元素x，已知p为其单链表存储结构中指向结点a的指针。

插入：

假设s为指向结点x的指针，则可用语句描述：s->next = p->next; p->next = s;

删除：

假设p为指向结点a的指针，则修改指针的语句为： p->next = p->next->next;

实现：

 1 function listInsert(i, data) {
 2     var j = 0;
 3     var p = this;
 4     // 寻找第i-1个节点
 5     while (p && j < i - 1) {
 6       p = p.next;
 7       ++j;
 8     }
 9     // i < 1或者大于表长+1
10     if (!p || j > i - 1) return false;
11     // 生成新节点，插入p节点后面
12     p.next = new LNode(data, p.next);
13     return true;
14   }
15 
16 function listDelete(i) {
17     var j = 0;
18     var p = this;
19 
20     while (p.next && j < i - 1) {
21       p = p.next;
22       ++j;
23     }
24 
25     if (!p.next || j > i - 1) return false;
26     var q = p.next;
27     p.next = q.next;
28     return q.data;
29   }

单链表的其他操作

逆位序输入n个元素的值，建立带表头结点的单链线性表L。

function createList_L(n) {
  var deferred = require(‘rsvp‘).defer();
  var l = new LNode();
  var count = n;
  process.stdin.setEncoding(‘utf8‘);

  process.stdin.on(‘data‘, function handler(data) {
    console.log(123);
    data = data.replace(‘\n‘, ‘‘);
    l.next = new LNode(data, l.next);
    if (!(--count)) {
      console.log(‘pausing‘);
      process.stdin.pause();
      deferred.resolve(l);
    }
  });

  return deferred.promise;
}

假设头指针为La和Lb的单链表分别为线性表LA和LB的存储结构，先要归并La和Lb得到单链表Lc：

 1 function mergeList(a, b) {
 2   var pa = a.next;
 3   var pb = b.next;
 4   // 用a的头结点作为c的头结点
 5   var c = a;
 6   var pc = a;
 7 
 8   while (pa && pb) {
 9     if (pa.data <= pb.data) {
10       pc.next = pa;
11       pc = pa;
12       pa = pa.next;
13     } else {
14       pc.next = pb;
15       pc = pb;
16       pb = pb.next;
17     }
18   }
19 
20   // 插入剩余段
21   pc.next = pa ? pa : pb;
22 
23   return c;
24 }

完整代码：

  1 // 单链表
  2 /*
  3 线性链表存储结构
  4 整个链表的存取必须从头指针开始进行，头指针指示链表中第一个结点（即第一个数据元素的存储映像）的存储位置。
  5 同时，由于最后一个数据元素没有直接后继，则线性链表中最后一个结点的指针为空null。
  6 */
  7 
  8 function LNode(data, node) {
  9   this.data = data;
 10   this.next = node || null;
 11 }
 12 LNode.prototype = {
 13   // 时间复杂度O(n)
 14   getElem: function getElem(i) {
 15     // 初始化，p指向第一个节点，j为计数器
 16     var p = this.next;
 17     var j = 1;
 18     // 顺指针向后查找，知道p指向第i个元素或p为空
 19     while (p && j < i) {
 20       p = p.next;
 21       ++j;
 22     }
 23     // 第i个元素不存在
 24     // 或者取第i个元素
 25     return (!p || j > i) ? null : p.data;
 26   },
 27   // 时间复杂度O(n)
 28   listInsert: function listInsert(i, data) {
 29     var j = 0;
 30     var p = this;
 31     // 寻找第i-1个节点
 32     while (p && j < i - 1) {
 33       p = p.next;
 34       ++j;
 35     }
 36     // i < 1或者大于表长+1
 37     if (!p || j > i - 1) return false;
 38     // 生成新节点，插入p节点后面
 39     p.next = new LNode(data, p.next);
 40     return true;
 41   },
 42   listDelete: function listDelete(i) {
 43     var j = 0;
 44     var p = this;
 45 
 46     while (p.next && j < i - 1) {
 47       p = p.next;
 48       ++j;
 49     }
 50 
 51     if (!p.next || j > i - 1) return false;
 52     var q = p.next;
 53     p.next = q.next;
 54     return q.data;
 55   }
 56 };
 57 
 58 LNode.createList_L = function createList_L(n) {
 59   var deferred = require(‘D:\\node\\node_modules\\rsvp‘).defer();
 60   var l = new LNode();
 61   var count = n;
 62   process.stdin.setEncoding(‘utf8‘);
 63 
 64   process.stdin.on(‘data‘, function handler(data) {
 65     console.log(123);
 66     data = data.replace(‘\n‘, ‘‘);
 67     l.next = new LNode(data, l.next);
 68     if (!(--count)) {
 69       console.log(‘pausing‘);
 70       process.stdin.pause();
 71       deferred.resolve(l);
 72     }
 73   });
 74 
 75   return deferred.promise;
 76 };
 77 
 78 function deepCopy(obj) {
 79   var newObj = {};
 80 
 81   for (var i in obj) {
 82     if (typeof obj[i] === ‘object‘) {
 83       newObj[i] = deepCopy(obj[i]);
 84     } else {
 85       newObj[i] = obj[i];
 86     }
 87   }
 88 
 89   return newObj;
 90 }
 91 
 92 // TODO
 93 /*
 94 已知单链线性表a和b的元素按值非递减排列。
 95 归并a和b得到新的单链线性表c，c的元素也按值非递减排列。
 96 */
 97 LNode.mergeList = function mergeList(a, b) {
 98   var pa = a.next;
 99   var pb = b.next;
100   // 用a的头结点作为c的头结点
101   var c = a;
102   var pc = a;
103 
104   while (pa && pb) {
105     if (pa.data <= pb.data) {
106       pc.next = pa;
107       pc = pa;
108       pa = pa.next;
109     } else {
110       pc.next = pb;
111       pc = pb;
112       pb = pb.next;
113     }
114   }
115 
116   // 插入剩余段
117   pc.next = pa ? pa : pb;
118 
119   return c;
120 };
121 
122 function log(list) {
123   var arr = [];
124 
125   do {
126     arr.push(list.data);
127     list = list.next;
128   } while (list);
129 
130   console.log(arr.join(‘,‘));
131 }
132 
133 void function test() {
134   var a1 = new LNode(1);
135   a1.listInsert(1, 2);
136   a1.listInsert(2, 3);
137   a1.listInsert(1, 4);
138   console.log(a1.getElem(1));
139   console.log(a1);
140   log(a1);
141   a1.listDelete(1);
142   console.log(‘a1 linkList:‘);
143   console.log(a1);
144   log(a1);
145   /*
146       LNode.createList_L(5)
147         .then(function(list){
148           console.log(list);
149         });
150       */
151   var a2 = new LNode(3);
152   a2.listInsert(1, 3);
153   a2.listInsert(2, 8);
154   a2.listInsert(1, 4);
155   a2.listDelete(2);
156   console.log(‘a2 linkList‘);
157   log(a2);
158 
159   var a3 = LNode.mergeList(a2, a1);
160   console.log(‘merging linkLists‘);
161   console.log(a3);
162   log(a3);
163 }();