algorithm - 使用指针和链表 : how to iterate over a linked list, 更改和比较键

Question

我被要求实现一个基于 linkedList 的数据结构的算法。以伪代码的形式。

不幸的是，我有 Python/Java 背景，因此没有使用指针的经验。

有人能解释一下我将如何遍历 doublyLinkedList 吗？ ，更改和比较元素的值。

根据我目前的理解，我会做这样的事情:对每个元素进行迭代。

for L.head to L.tail 

但是我将如何访问类似于 A[i] for i to L.length 的列表中的当前对象？ ？

作为 order of a linkedList is determined by pointers rather than indices in a linkedList我可以简单地做类似 currentObj.prev.key = someVal 的事情吗或 currentObj.key < currentObj.prev.key还是有其他一些工作流程可以处理单个元素？

同样，我显然被困住了，因为我对如何处理指针缺乏基本的了解。

干杯，安德鲁

Answer 1

所以基本上数据结构是:

• 节点:

  node {
    node next;//"single link"
    node prev;//for "doubly"...
  }
  

• 和列表:

  list {
     node head;//for singly linked, this'd be enough
     node tail;//..for "doubly" you "point" also to "tail"
     int/*long*/ size; //can be of practical use
  }
  

列表的(常见)操作:

• 创建/初始化:

  list:list() {
      head = null;
      tail = null;
      size = 0;
  }
  

• 在第一个位置添加一个节点:

  void:addFirst(node) {
     if(isEmpty()) {
       head = node;
       tail = node;
       size = 1;
     } else {
       head.prev = node;
       node.next = head;
       head = node;
       size++;
     }
  }
  // ..."add last" is quite analogous...
  

• “为空”，可以用不同的方式实现..只要你保持不变

  bool:isEmpty() {
      return size==0;
      //or return head==null ... or tail==null
  } 
  

• “在位置 i 添加一个节点”:

  void:add(i, node) {
      assert(i>=0 && i <=size);//!
      if(isEmpty() || i == 0) { 
          addFirst(node);
      } else if (i == size) {
          addLast(node);
      } else {//here we could decide, whether i is closer to head or tail, but for simplicity, we iterate "from head to tail".
        int j = 1;
        node cur = head.next; //<- a "cursor" node, we insert "before" it ;) 
        while(j < i) {//1 .. i-1 
           cur = cur.next;// move the cursor
           j++;//count
        }
        //j == i, cur.next is not null, curr.prev is not null, cur is the node at currently i/j position
        node.prev = cur.prev;
        cur.prev.next = node;
        cur.prev = node;
        node.next = cur;
     }
     //don't forget the size:
     size++;
  }
  

• 删除(节点)很简单!

• “删除位置”、“查找节点”、“按位置获取节点”等应该使用类似的循环(如add(i, node))...找到正确的索引或节点。

双链表(与单链表相比)的强度/优势在于它可以像“前向”和“后向”一样迭代。要利用这个优势(它只对基于索引的操作有利，对于“查找(节点)”，例如你仍然不知道从哪里开始/迭代最好)，你确定 pos 是否更接近到 head(0) 或 tail(size-1)，并相应地开始和路由您的迭代。

...您还对哪些操作感兴趣(详细信息)？