我被要求根据链表的数据结构以伪代码的形式实现一个算法。
不幸的是，我有Python / Java背景，因此没有指针的经验。
有人能解释一下如何迭代一个双向链表，更改和比较元素的值吗？
从我目前了解的情况来看，我会像这样做：对每个元素进行迭代。
for L.head to L.tail
那么，如何访问类似于A [i] for i to L.length的列表中的当前对象？
由于链表的顺序是由指针而不是索引决定的，我是否可以像这样做：currentObj.prev.key = someVal或currentObj.key < currentObj.prev.key，还是有其他工作流程来处理单个元素？
再次说明，由于缺乏有关指针处理的基本理解，我很明显陷入了困境。
祝好， 安德鲁
所以基本上数据结构包括：
Node:
node {
node next;//"single link"
node prev;//for "doubly"...
}
and List:
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
}
列表的常见操作：
Creation/Initialization:
list:list() {
head = null;
tail = null;
size = 0;
}
Add a node at the first position:
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...
"is empty", can be implemented in different ways..as long as you keep the invariant
bool:isEmpty() {
return size==0;
//or return head==null ... or tail==null
}
"add a node at position 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++;
}
Delete(node) is easy!
"Delete at position", "find node", "get node by position", etc. should use a similar loop (as add(i, node))...to find the correct index or node.
pos是更靠近头部（0）还是尾部（size-1），并相应地开始和路由您的迭代。