带索引的单向链表

Question

我想用来创建一个单链表。我已经有了一个不允许对其进行索引的实现。我想添加这个功能，但我不确定如何做。

​

​

所以基本上头部应该有索引"1“。但是我自己也搞不清楚，在If语句中，我应该怎么做才能让索引每一步都增加1。

void AddNode (int addData)
{
    nodePtr NewNode = new node;
    NewNode->next = NULL;
    NewNode->data = addData;

    if (head != NULL)
    {
        curr = head;
        while(curr->next != NULL)
        {
            curr = curr->next;
        }
        curr->next = NewNode;
        NewNode->index;
    }
    else
    {
        head = NewNode;
        NewNode->index = 1;
    }
}

Answer 1

您是说能够通过get(index)获取链表节点吗？

另外，你的头部不应该有索引1，它应该是0。这不符合从零开始编制索引的标准做法。

从技术上讲，链表没有索引，也不应该存储索引。看起来链表可能不是您正在做的事情的正确数据结构，但是您可以像这样使用循环来处理它(如果我的c++语法很生疏，请原谅)。

int get(int index) {
  Node current = head;
  for (int x = 0; x < index; x++) {
    if (current->next == null) {
      //some sort of error handling for index out of bounds
    } else {
      current = current->next;
    }
  }
  return current->data
}

get(2)将返回列表的第三个元素。

Answer 2

Graph for the structure为什么要将它添加到列表的末尾？只需将新节点添加到前面即可。

我认为没有必要遵循1，2，3的顺序。相反，您可以在添加新节点之前进行反向操作，您可以访问head并找到它的索引(I)。当您添加新的索引时，此索引将为i+1。

两个优点：-当你遍历这个列表时，它不会改变任何东西。-你知道你已经在这个列表中添加了多少。

Answer 3

因此，您真正想要做的是添加功能来索引链表的元素。

• 实际上没有必要将索引存储在任何地方(因为您并没有真正将array/vector元素的索引存储为类型，而数组第一个元素的地址就是检索i-th元素所需的全部内容)。
• 您想要保留的唯一信息是列表的长度，因为计算它的成本很高，因为每次需要它时，您都必须从head遍历列表到tail。获得此信息后，addNode应该只更新列表的size。

正如您已经知道的，访问链表的i-th元素的成本也很高(与向量相比)，但它很容易编码。

下面这样的代码应该是有效的：

void get(Node* head, size_t pos) {
    while (head && pos--)
        head = head->next;
    return pos<=0 ? head : nullptr ;
}

它从head开始遍历列表，直到到达末尾(head为nullptr)或pos为<=0。一旦退出循环，如果pos>0表示列表比pos短，否则可以返回head (它将指向pos-th元素)