Doubly Linked List - Array Implementation

Question

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.

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.

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

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

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

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]

Is that correct?

trincot trincot · Accepted Answer · 2021-03-16T13:48:25

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

Then the Delete function could be:

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

Doubly Linked List - Array Implementation

1 Answers