双向链表 - 数组实现 [英] Doubly Linked List - Array Implementation

问题描述

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

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.

我想实现删除函数，它接收一个值，然后从数组中删除它.

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屋！