singly-linked-list - 我怎样才能回到单链表？

Question

我有一个单链表。从列表中的每个节点，我可以到达下一个元素。是否有可能进入前一个元素？请注意，由于内存限制，我不能使用双向链表。

Answer 1

如果您必须使用单链表，那么解决此问题的一种方法是再次遍历列表，直到找到前一个项目。Next当它的字段等于当前项目时，您将知道您何时位于前一个项目。

伪 C 代码：

Node* GetPreviousNode(Node* currentNode)
{
    Node* iteratorNode = GetHeadNode();
    while (iteratorNode != NULL)
    {
        if (iteratorNode->Next == currentNode)
            return iteratorNode;

        iteratorNode = iteratorNode->Next;
    }
    return NULL;
}

Answer 2

你不能，你必须使用一个双链表，你有一个指向前一个和下一个元素的指针。单个链表只是指向下一个元素，不会跟踪之前的元素。

试试这个： http://en.literateprograms.org/Doubly_linked_list_(Java)

Answer 3

有两种不同的方法可以双向遍历单链表。

方法1：（结构的）链接字段实际上是一个“差异”字段。链接计算为下一项的地址减去上一项的地址，因此...

next = 上一项的地址 + 当前项的链接。prev = 下一项的地址 - 当前项的链接。

如果你能用指针做算术，你就会做生意。如果没有，您将不得不使用联合（在 C++ 中）或使用方法 2。请参阅：算法 + 数据结构 = Niklaus Wirth 的程序 - Prentice-Hall 1976 - 第 19 页。

方法2：链接字段是上一项的地址与下一项的地址的'异或'（^）。异或是自身的逆，因此...

next = 上一项的地址 ^ 当前项的链接。prev = 下一项的地址 ^ 当前项的链接。

Answer 4

如果您有一个确定的节点，在单链表中的给定节点之前，那么您可以创建一个函数：-

    struct node* prev(struct node* before, struct student_detail* current)
    {
        struct student_detail* temp = before;
        while (temp->next != NULL)
        {
            if(temp->next == current)
            {
                return temp;
            }

            temp = temp-> next;
        }
        return NULL;
    }

并使用它

    example_node = prev(before, example_node);

如果你有 head，你总是可以将它用作 prev 节点。

Answer 5

从理论上讲，您可以返回，它通常击败了单链表背后的整个概念，并且比必要的麻烦更多，但是如果必须这样做，这是在 C 中实现它的方法，当然，假设您已经声明了 Node 结构：-

Node* go_back(Node* head, Node* current_node){
   //Traverse the linked list until we discover the next node
   //in our traversal points to our current node
   Node* previous_node = head;
   while(previous_node->next != NULL){
       if(previous_node->next == current_node)
           return previous_node->next; //found previous node
       previous_node = previous_node->next;
   } 
   return previous_node //we found nothing, give up
}