双链表-阵列实现 [英] Doubly Linked List - Array Implementation

问题描述

我刚刚开始研究数据结构，我需要了解双向链表，该链表由3个数组(数据，下一个，上一个)实现.

I have just started to study data structures, and I need to understand doubly-linked list, which is implemented by 3 arrays - Data, Next, Prev.

我想实现delete函数，该函数接收一个值，并将其从数组中删除.

I want to implement delete function, which receives a value, and deletes it from the array.

我有一个指向列表开头的指针L和一个指向数据数组中第一个空闲元素的FREE指针.

I have a pointer L to the head of the list, and a pointer FREE, that points to the first free element in the Data array.

我想实现它，我知道我需要更新所有3个数组.

I want to implement it, and I know that I need to update all 3 of the arrays.

这是我在psu中尝试删除的第一个元素:

Here is my attempt in psu to delete the first element:

Delete(value)
   if L == -1 : return -1
   if D[L] == value:
      temp = N[L]
      N[L] = FREE
      FREE = L
      L = temp

上面的代码不会更新P(Prev)数组.

The above code doesn't update the P (Prev) array.

我不确定应该如何更新P，但这是我认为应该做的:

I'm not sure how should I update P, but this is what I think I should do:

Delete(value)
   if L == -1 : return -1
   if D[L] == value:
      P[FREE] = L
      temp = N[L]
      N[L] = FREE
      FREE = L
      L = temp 
      P[L] = P[FREE]

对吗?

推荐答案

您将首先编写一个函数以查找列表中的值:

You would first write a function to find the value in the list:

Find(value)
    node = L
    while node != -1:
        if D[node] == value:
           return node
        node = N[node]
    return -1

然后删除功能可以是:

Delete(value)
    node = Find(value)
    if node == -1:
        return -1
    D[node] = 0  # optional wipe of the data
    # Adjust the links that are TOWARDS the deleted node
    if node == L:
        L = N[node]  # first node is deleted
    else:
        N[P[node]] = N[node]
    if N[node] != -1:
        P[N[node]] = P[node]
    # Adjust the links FROM the delete node
    P[node] = -1;
    N[node] = FREE
    # Prepend to FREE list
    P[FREE] = node
    FREE = node
    return node

这篇关于双链表-阵列实现的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！