Need help in understanding the pseudocode function that aims to delete an element in a specified memory address in a linked list

Question

I was studying about Linked Lists from the book, "Introduction to Algorithms" by T Cormen.

There was an portion in the book as follows:

Given an element x in the list, x.next points to its successor in the linked list, and x.prev points to its predecessor.

If x.prev=NIL, the element x has no predecessor and is therefore the first element, or head, of the list. If x.next=NIL, the element x has no successor and is therefore the last element, or tail, of the list. An attribute L.head points to the first element of the list. If L.head=NIL, the list is empty.

The procedure LIST-DELETE removes an element x from a linked list L. It must be given a pointer to x, and it then “splices” x out of the list by updating pointers.

LIST-DELETE(L,x)
1 if x.prev!= NIL
2 x.prev.next = x.next
3 else L.head = x.next
4 if x.next !=
 NIL
5 x.next.prev = x.prev

---

However, I did not get any of the portions in the text. First of all, they check whether the next possible memory address contained in x is NIL or not. If it is not NIL, then they replace x.prev.next by x.next. Now, x.prev.next is just a function that returns the memory address of x.key i.e returns the address in x. This means x.prev.next and x are the same. Finally, the statement x.prev.next=x.next seems nonsensical and absurd because x.prev.next is not a variable but a function that returns a value and assigning a new value to a "function return statement" makes no sense. So, I think, they tried to imply x=x.next and thus, the memory address in x becomes equal to the memory address of the next element after x.key.

Next, they check if, x.prev is equal to NIL this means, that x=L.head. Under this scenario, we change L.head to x.next i.e make the list start from the element after x.key. So, the element in memory address contained in x gets deleted.

Finally, it seems they check if x.next equal to NIL. If it is not, then, x.next.prev(=x)=x.prev.

Thus, the memory address stored in x gets replaced by the memory address returned by x.prev.

But I don't really have a clue how the real job of deletion of the element in the address contained in x, gets done. I have no idea about this.

Answer 1

i don't know about that book, but the problem with deleting elements inside a liked list is that you may destroy the link between the elements (because if you delete x then x.prev can't reach x.next and the list is now technically seperated into two lists).

to solve this problem we need to attach x.prev to x.next so x.prev.next is equal to x.next so we can delete x safely.

if you have a head or a tail in your linked list that points to the start and end of the list then you should be aware when deleting these elements.

if you are deleting the first element (lets say x) then you need to make head equal to x.next

but if you are deleting the last element then tail should be equal to x.prev.

Answer 2

The data at the memory address contained in x doesn't get deleted directly. Only the reference to x from the previous and next elements gets deleted. This allows the memory associated with x to be reclaimed by the system (assuming there are no other references to it). The actual deletion of the memory occupied by x is typically managed by the memory management system of whatever programming language you use.

Keep in mind that this is Pseudocode, it is not written in any specific language and not meant to actually run. It's only intended to explain the idea of how the pointers are changed so that the deleted element is not referenced anymore.

Python and Java for example use reference counting, meaning they keeps track of how many references exist to an object. When the reference count drops to zero, it means that this object is no longer accessible from anywhere, so the garbage collector can safely reclaim its memory. This is done automatically so you don't have to think or do anything about it.

In C, memory is managed manually, so you have to explicitly allocate and deallocate memory. After you have removed all the references to your element you would release the memory explicitly with free(pointer_to_element).

EDIT: Initially x.prev.next == x.next.prev == x, as in next of the element before x points to x, and prev of the element after x points to x. In the second row of the pseudocode (x.prev.next = x.next) this is changed: next of the element before x now points to the element after x. In the last row (x.next.prev = x.prev) the pointer prev of the element after x now points to the element before x.

You can imagine that each element of the queue is saved at some location. In the table below I put the locations next to each other, but that's not necessary.

location	0	1	2
element	A	X	B
prev	NIL	0	1
next	1	2	NIL

Initially we have this setup:

L.head = 0 (--> points to A as the first element of the queue)
A.prev = NIL (because it's at the start of the queue)
A.next = 1 (--> points to X)
X.prev = 0 (--> points to A)
X.next = 2 (--> points to B)
B.prev = 1 (--> points to X)
B.next = NIL (because it's at the end of  the queue)

Now we execute your program step by step: X.prev is not NIL, so the second row is executed. After the second row the pointers will look like this (only A.next has changed):

| location | 0 | 1 | 2 | |----------|---|---|---| | element | A | X | B | | prev | NIL | 0 | 1 | | next | 2 | 2 | NIL | The else statement on line 3 is not executed since the if statement was true. In line 4, X.next is indeed not NIL, so line 5 is executed. After that the pointers will look like this (only B.prev has changed):

location	0	1	2
element	A	X	B
prev	NIL	0	0
next	2	2	NIL

Note that X still exists, and none of its own pointers have changed. This doesn't matter, since X is not reachable from the start of the queue (L.head) anymore. If we now traverse the list by following the pointers this happens:

L.head points to location 0, we go there and find element A
A.next points to location 2, we go there and find element B
B.next points to NIL, so we know we have reached the last element and are done

This also works if the locations do not correspond to the position in the list. I kept the order of the list (A -> X -> B), so L.head points to 5 (because A is the first element in the queue):

location	0	1	2	3	4	5
element	none	X	none	none	B	A
prev	none	5	none	none	1	NIL
next	none	4	none	none	NIL	1

If we run the algorithm on this list, the result will look like this:

location	0	1	2	3	4	5
element	none	X	none	none	B	A
prev	none	5	none	none	5	NIL
next	none	4	none	none	NIL	4

Again only A.next and B.prev changed.