我被要求实现一个基于 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
还是有其他一些工作流程可以处理单个元素?
同样,我显然被困住了,因为我对如何处理指针缺乏基本的了解。
干杯, 安德鲁
最佳答案
所以基本上数据结构是:
节点:
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),并相应地开始和路由您的迭代。
...您还对哪些操作感兴趣(详细信息)?
关于algorithm - 使用指针和链表 : how to iterate over a linked list, 更改和比较键,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/29956466/