双向链表 - 数组实现
Doubly Linked List - Array Implementation
刚开始学习数据结构,需要了解双向链表,它由3个数组实现——Data、Next、Prev
我想实现删除函数,它接收一个值,并将其从数组中删除。
我有一个指向列表头部的指针 L 和一个指向数据数组中第一个空闲元素的指针 FREE。
我想实现它,我知道我需要更新所有 3 个数组。
这是我在 psu 中删除第一个元素的尝试:
Delete(value)
if L == -1 : return -1
if D[L] == value:
temp = N[L]
N[L] = FREE
FREE = L
L = temp
以上代码没有更新 P (Prev) 数组。
我不确定我应该如何更新 P,但这是我认为我应该做的:
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]
对吗?
您首先要编写一个函数来查找列表中的值:
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
刚开始学习数据结构,需要了解双向链表,它由3个数组实现——Data、Next、Prev
我想实现删除函数,它接收一个值,并将其从数组中删除。
我有一个指向列表头部的指针 L 和一个指向数据数组中第一个空闲元素的指针 FREE。
我想实现它,我知道我需要更新所有 3 个数组。
这是我在 psu 中删除第一个元素的尝试:
Delete(value)
if L == -1 : return -1
if D[L] == value:
temp = N[L]
N[L] = FREE
FREE = L
L = temp
以上代码没有更新 P (Prev) 数组。
我不确定我应该如何更新 P,但这是我认为我应该做的:
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]
对吗?
您首先要编写一个函数来查找列表中的值:
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