Linear doubly linked (bidirectional) list. General concepts

This topic describes the basic operations performed on a linear doubly linked (bidirectional) list. A continuation of this topic is a practical example of the implementation of the List<T> class, which can be found at the following link:

Linear doubly linked list. Example of a template class

1. General view of a doubly linked list. The main element of the list. Figure
2. List creation
3. Adding an element to the end of a list
- 3.1. Adding a new element to the end of empty list
- 3.2. Adding a new element to a list that already has elements
4. Inserting an element at a given position in a list
- 4.1. Inserting the element at the first position of a list containing elements
- 4.2. Inserting an element in the middle of a list containing elements
5. Removing the element from the list
Related topics

Search other resources:

1. General view of a doubly linked list. The main element of the list. Figure

In a doubly linked list, the base element of the list (node) has the following fields:
– data – data. Data can be any value of any type;
– next – pointer to the next element;
– prev is a pointer to the previous element.

Рисунок 1. Базовый элемент списка

In C++ (and other languages), a doubly linked list is created by developing a special class. In the class, the underlying data representing the list is:

begin – pointer to the first element of the list;
end – pointer to the last element of the list;
count is the number of elements in the list.

The general view of a doubly linked list is shown in Figure 2.

Figure 2. General view of a doubly linked list

⇑

2. List creation

Before adding new elements to the list, the first priority is to create an empty list.
When creating a list, the following steps can be distinguished:

declaration of pointers to the beginning and end of the list (begin, end);
setting null values for pointers;
setting the length of the list (count) to zero.

Figure 3. List creation. Stage 1 – declaration of internal variables. Stage 2 – Filling variables with zero values

⇑

3. Adding an element to the end of a list

When adding an element to the end of the list, the following two situations are distinguished:

adding the element to an empty list;
adding an element to a non-empty list (a list containing elements).

⇑

3.1. Adding a new element to the end of empty list

The process of adding an element to the end of an empty list consists of the following steps:

create a new elem element and fill it with data (Figure 4);
set the beginning and end of the list (begin, end) so that they point to the new element elem (Figure 5);
increase the total number of elements in the list (count field).

Figure 4. Create an element and fill in the data. The next, prev and data fields of the elem element are filled

In Figure 5, the begin and end pointers are set to point to the newly created elem.

Figure 5. Adding the element to empty list. Setting the start and end pointers of the list

⇑

3.2. Adding a new element to a list that already has elements

Adding a new element to an empty list consists of the following steps:

creation of a new element elem. Filling in the data and next fields of the element (Figure 6);
setting the prev pointer of the elem element in such a way that it points to the current position of the end pointer of the list (Figure 7);
setting the next pointer of the last end element so that it points to the elem element (Figure 7);
offset of the pointer to the end of the list elem by one position, determined by the pointer elem.

Figure 6. Create the element. Setting the next pointer and data field of the elem element

Figure 7. Adding an element to the end of a non-empty list. Setting the prev pointer of the elem element and the next pointer of the last element (end) of the list

Figure 8. Adding an element to the end of a non-empty list. Set the list end pointer (end) to the last position

⇑

4. Inserting an element at a given position in a list

Unlike the operation of adding an element to the end of the list, there is an operation of inserting an element into the list. If an element is inserted into an empty list, then this operation is the same as adding an element to an empty list (see clause 3.1).

When inserting an element into a list containing elements, the insertion position is important. Depending on the position, the following situations are considered:

the element is inserted in the first position of the list;
the element is inserted into the second, third, etc. the position of the list, as well as the last position of the list;
the element is inserted after the last position of the list. In this case, this insertion is the same as adding an element to the end of a non-empty list (as described in clause 3.2).

⇑

4.1. Inserting the element at the first position of a list containing elements

The sequence of actions when inserting an element at the first position of the list is as follows:

create an element and fill it with data (Figure 9). The data and prev fields are filled;
set the next pointer of the elem element to the first element in the begin list (Figure 10);
set the pointer prev of the first element of the list to the inserted element elem (Figure 11);
redirect the begin pointer so that it points to the new element elem (Figure 12);
increase the total number of list elements.

Figures 9, 10, 11, 12 show the above steps in a visualized form.

Figure 9. Insert an element at the beginning of a non-empty list. Creating a new elem

Figure 10. Setting the next pointer of the inserted element

Figure 11. Assigning the prev pointer to the first element of the begin list to be inserted, the address of the element elem

Figure 12. Insert an element at the beginning of the list. Redirecting the begin pointer to the address of the elem element

⇑

4.2. Inserting an element in the middle of a list containing elements

To insert an element in the middle of the list at some position index, you need to perform the following sequence of steps:

get the elemPrev element that comes before the insertion position. In other words, get the element at position index-1 (Figure 13);
get the elemCur element placed at the index insertion position (Figure 13);
create a new element elemIns, which will be inserted between the elements elemPrev and elemCur. Fill in the data field of the element (Figure 14);
set the next pointer of the element elemIns equal to the address of the element elemCur (Figure 15);
set the prev pointer of the elemIns element to the address of the elemPrev element (Figure 15);
move the next pointer of the elemPrev element to the elemIns element (Figure 16);
move the prev pointer of the elemCur element to the elemIns element (Figure 16).

The above step-by-step process is shown in Figures 13, 14, 15, 16.

Figure 13. Inserting an element into a non-empty list. Get elements at positions index-1 and index

Figure 14. Inserting an element into a non-empty list. Creating a new element. Filling in the data field

Figure 15. Inserting an element into a non-empty list. Setting the pred and next pointers of the insertion element

Figure 16. Inserting an element into a non-empty list. Redirecting the next pointer of the previous elemPrev element and the prev pointer of the next elemCur element to the inserted elemIns element

⇑

5. Removing the element from the list

When removing the element from the list containing elements, three possible situations are considered:

the first element of the list is removed;
not the first and not the last element is deleted;
the last element of the list is removed.

⇑

5.1. Removing the first element from a list

When removing the first element from the list, the sequence of steps is as follows:

save the address of the first element in the value elem (Figure 17);
change the value of the begin pointer so that it points to the next element (Figure 18). If there is no next element, then the pointer will be nullptr;
set the value of the prev pointer to zero (Figure 19);
release the memory allocated for the elem element;
decrease the total number of parts by 1.

If there is only one element in the list, then the above steps will also work for this case. Figures 17, 18, 19, 20 below show the main steps of this process.

Figure 17. Removing the first element from the list. Step 1. Save the value of the beginning of the list (begin)

Figure 18. Removing the first element from the list. Step 2. Move the begin pointer to the next element

Figure 19. Removing the first element from the list. Step 3. Setting the pointer prev of the beginning of the list (begin) to zero

Figure 20. Removing the first element from the list. Destroying the elem element (freeing memory)

⇑

5.2. Removing from the middle of the list

If an element is removed from the middle of the list, then the sequence of steps is as follows:

based on the element index (index), get a pointer to the elem element to be deleted, as well as to the previous elemPrev and next elemNext elements (Figure 21);
set the next pointer of the elemPrev element to the address of the elemNext element (Figure 22);
set the prev pointer of the elemNext element to the address of the elemPrev element (Figure 22);
delete element (free memory allocated for element) elem (Figure 23).

Figure 21. Removing the element from the list. Step 1: Get the element to be removed and the previous and next elements

Figure 22. Removing an element from the list. Step 2. Setting the pointers to the previous element elemPrev and the next element elemNext, bypassing the elem element

Figure 23. Removing the element from the list. Step 3: Removing the elem element

⇑

5.3. Removing the last element from a list

To remove the last element from the list, the following sequence of actions is performed:

store the address of the last element in the list in the elem pointer;
move to the previous element the end pointer pointing to the last element in the list;
release the memory allocated for the last element in the list;
set the next pointer of the end element to zero.

The operation of removing the last element from the list is suitable for the case when there is only one element in the list.

Figure 24. Remove the last element from the list. Remember the address of the last element

Figure 25. Removing the last item from the list. Move the end pointer to the previous element of the list

Figure 26. Remove the last element from the list. Freeing the memory allocated for the last element

Figure 27. Remove the last element from the list. Setting the next pointer to the last element of the list to zero

BestProg

Programming: theory and practice