我被要求以伪代码的形式实现一个基于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之类的事情吗？或者有其他工作流程可以处理单个元素吗？
再一次，我显然陷入了困境，因为我对如何处理指针缺乏基本的理解。
干杯，Andrew
所以基本上数据结构是：
-
节点：
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))。。。以找到正确的索引或节点。
双链表(与单链表相比)的优势在于，它可以像"前"one_answers"后"一样迭代。要使用这一优势(它只对基于索引的操作有利，对于"find(node)"，例如，您仍然不知道从哪里开始/迭代最好)，您可以确定pos是更接近head(0)还是更接近tail(size-1)，并启动&相应地安排迭代。
你还参与了哪些操作(细节)？