数组双向链表-函数实现

Question

刚开始学习数据结构，需要了解双向链表，它是由3个数组实现的——Data、Next、Prev

我想实现 Find 函数，它接收一个值，return这个值在列表中的索引位置（而不是在 Data 数组中）。

我知道我有一个指向列表第一个元素的指针，但我很难return指向所需值的指针。

这是我在 psu 中的尝试：

Find(value)
   for i=0 to D.length
      if D[i] == k
   return ?
 return -1

我不知道应该用什么 return 而不是问号 (?)。

例如，如果我的列表看起来像这样：1 -> 2 -> 3 -> 4，但数组显然不必按照列表的相同方式排序，那么 Find(1) 将 return 0，Find(3) 将 return 2...

任何帮助都会很棒！

谢谢！

Answer 1

首先，你应该复习一下链表的基础知识，因为你不可能事先知道链表的长度。因此，如果您不存储列表的长度，则 D.length 在您使用整个列表之前无法确定。

function find(value)
    while pointer.next is not null (this is the indication you reached the end)
        check if pointer.value is your desired value
            return pointer
        else
            pointer = pointer.next (move your pointer)

数组双向链表-函数实现

Array Doubly Linked List - Function Implementation

arrays

arraylist

data-structures

linked-list

doubly-linked-list