List 链表

List

List - 图1

CBrother链表是双向链表，每个元素都知道自己前面的元素与后面的元素，可以快速删除于插入，但是无法直接通过下标访问。

函数描述参数返回值用法
addFirst(obj) 添加元素到链表头 obj：要添加的元素 无 myList.addFirst(5)
addLast(obj) 添加元素到链表尾 obj：要添加的元素 无 myList.addLast(4)
size() 获取链表长度 无 链表元素个数 var nowsize = myList.size()
popFirst() 移除链表头元素，第二个节点设为头 无 被移除的元素 var delobj = myList.popFirst()
popLast() 移除链表尾元素，倒数第二节点设为尾 无 被移除的元素 var delobj = myList.popLast(1)
clear() 清空链表 无 无 myList.clear()
begin() 开始从头遍历链表 无 无 myList.begin()
end() 开始从尾遍历链表 无 无 myList.end()
get() 遍历中获取当前节点 无 当前节点 var obj = myList.get()
pop() 遍历中删除当前节点,跳入便利顺序的下一节点 无 被移除的元素 myList.pop()
next() 遍历中跳入后面一个节点 无 false:到最尾了,true:成功 myList.next()
fornt() 遍历中跳入前面一个节点 无 false:到头了,true:成功 myList.fornt()
insertFornt(obj) 遍历中在前面插入一个元素 obj：要添加的元素 无 myList.insertFornt(5)
insertNext(obj) 遍历中在后面插入一个元素 obj：要添加的元素 无 myList.insertNext(5)

例子:

  1. function main(parm)
  2. {
  3.     var myList = new List();
  4.     myList.addLast(5);
  5.     myList.addLast(4);
  6.     myList.addLast(3);
  8.     var len = myList.size();
  9.     print "myList size:" + len;
  11.     var idx = 0;    
  12.     myList.begin();
  13.     do
  14.     {
  15.         print "myList " + idx + ":" + myList.get();
  16.         idx++;
  17.     } while(myList.next());
  19.     myList.addFirst(10);
  20.     myList.addFirst(11);
  22.     len = myList.size();
  23.     print "after addFirst. myList size:" + len;    
  25.     idx = 0;
  26.     myList.begin();
  27.     do
  28.     {
  29.         print "myList " + idx + ":" + myList.get();
  30.         idx++;
  31.     } while(myList.next());
  33.     myList.popFirst();
  34.     myList.popLast();
  36.     len = myList.size();
  37.     print "after pop. myList size:" + len;
  39.     idx = len - 1;
  40.     myList.end();    //倒序遍历
  41.     do
  42.     {
  43.         print "myList " + idx + ":" + myList.get();
  44.         idx--;
  45.     } while(myList.fornt());
  47.     myList.clear();
  48.     len = myList.size();
  49.     print "after clear. myList size:" + len;    
  50. }

结果:

  1. myList size:3
  2. myList 0:5
  3. myList 1:4
  4. myList 2:3
  5. after addFirst. myList size:5
  6. myList 0:11
  7. myList 1:10
  8. myList 2:5
  9. myList 3:4
  10. myList 4:3
  11. after pop. myList size:3
  12. myList 2:4
  13. myList 1:5
  14. myList 0:10
  15. after clear. myList size:0

例子2:

  1. function main(parm)
  2. {
  3.     var myList = new List();
  4.     myList.addLast(5);
  5.     myList.addLast(4);
  6.     myList.addLast(3);
  8.     var len = myList.size();
  9.     print "myList size:" + len;    
  11.     var idx = 0;    
  12.     myList.begin();
  13.     do
  14.     {
  15.         print "myList " + idx + ":" + myList.get();
  16.         idx++;
  17.     } while(myList.next());    
  19.     myList.begin();
  20.     do
  21.     {
  22.         var obj = myList.get();
  23.         if(obj == 4)
  24.         {
  25.             myList.insertFornt(100);        //4前面插入100 后面插入200
  26.             myList.insertNext(200);
  27.             break;
  28.         }
  29.     } while(myList.next());
  31.     var len = myList.size();
  32.     print "after insert.myList size:" + len;
  34.     idx = 0;
  35.     myList.begin();
  36.     do
  37.     {
  38.         print "myList " + idx + ":" + myList.get();
  39.         idx++;
  40.     } while(myList.next());
  43.     print "========================";
  45.     idx = 0;
  46.     myList.begin();
  47.     do
  48.     {
  49.         var obj = myList.get();
  50.         if(obj == 4)
  51.         {
  52.             myList.pop(); //正序遍历,自动跳入后面一个节点,所以要结束本地循环，因为继续执行myList.next()会多跳过一个节点，导致结果错误。
  53.             continue;
  54.         }
  55.         print "myList " + idx + ":" + myList.get();
  56.         idx++;
  57.     } while(myList.next());    
  59.     len = myList.size();
  60.     print "after pop. myList size:" + len;    
  62.     idx = len - 2;    //因为下面要删除一个节点，所以多减了1，让序号打印正确
  63.     myList.end();
  64.     do
  65.     {
  66.         var obj = myList.get();
  67.         if(obj == 100)
  68.         {
  69.             myList.pop(); //倒序遍历,自动跳入后面一个节点,所以要继续执行myList.fornt()
  70.         }    
  71.         print "myList " + idx + ":" + myList.get();
  72.         idx--;
  73.     } while(myList.fornt());    
  74. }

结果:

  1. myList size:3
  2. myList 0:5
  3. myList 1:4
  4. myList 2:3
  5. after insert.myList size:5
  6. myList 0:5
  7. myList 1:100
  8. myList 2:4
  9. myList 3:200
  10. myList 4:3
  11. ========================
  12. myList 0:5
  13. myList 1:100
  14. myList 2:200
  15. myList 3:3
  16. after pop. myList size:4
  17. myList 2:3
  18. myList 1:200
  19. myList 0:5

以上的遍历方法在多线程读的情况下也要加锁，比如线程1调用了next()，线程2又调用了begin(),那么线程1将获取不到自己想要的值。foreach可以解决这个问题。

foreach支持

foreach语句中的key表示当前遍历第几个元素,建议逻辑上不要依赖于这个值,value表示这个元素

  1. function main(parm)
  2. {
  3.     var myList = new List();
  4.     myList.addLast(5);
  5.     myList.addLast(4);
  6.     myList.addLast(3);
  8.     foreach(k,v : myList)
  9.     {
  10.         print "k:" + k + ",v=" + v;
  11.     }    
  12. }

结果:

  1. k:0,v=5
  2. k:1,v=4
  3. k:2,v=3