C++. Linear doubly linked (bidirectional) list. General concepts

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:


Contents


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.

C++. Linear doubly linked list. Base element of the list

Рисунок 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.

General view of a doubly linked list

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.

 

C++. Linear doubly linked list. Create a listFigure 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).

 

C++. Linear doubly linked list. Adding an element to the end of the list. Step 1. Creating an element and filling it with dataFigure 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.

C++. Linear doubly linked list Adding an element to the end of an empty list. Step 2. Set up pointers to the beginning and end of the list

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.

 

C++. Linear doubly linked list Adding an element to the list. Step 1: Create an elementFigure 6. Create the element. Setting the next pointer and data field of the elem element

C++. Linear doubly linked list. Adding an element to the list. Step 2. Set up pointersFigure 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

C++. Linear doubly linked list Adding an element to the list. Step 3. Setting the pointer to the last element of the listFigure 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.

C++. Linear doubly linked list Inserts an element at the first position of the list. Step 1: Create an elementFigure 9. Insert an element at the beginning of a non-empty list. Creating a new elem

C++. Linear doubly linked list Inserts an element at the first position of the list. Step 2. Setting the insertion element's next pointerFigure 10. Setting the next pointer of the inserted element

C++. Linear doubly linked list Inserts an element at the first position of the list. Step 3. Setting the pointer to the beginning of the listFigure 11. Assigning the prev pointer to the first element of the begin list to be inserted, the address of the element elem

C++. Linear doubly linked list Inserts an element at the first position of the list. Step 4. Setting the pointer to the beginning of the listFigure 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.

C++. Linear doubly linked list Insert an element into the list. Step 1. Get elements at insertion positionsFigure 13. Inserting an element into a non-empty list. Get elements at positions index-1 and index

C++. Linear doubly linked list. Inserting an element into a list. Step 2. Create a new elementFigure 14. Inserting an element into a non-empty list. Creating a new element. Filling in the data field

C++. Linear doubly linked list. Inserting an element into a list. Step 3: Set up the insertion element pointersFigure 15. Inserting an element into a non-empty list. Setting the pred and next pointers of the insertion element

C++. Linear doubly linked list. Inserting an element into a list. Step 4. Set up pointers of neighboring elementsFigure 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.

C++. Linear doubly linked list. Removing the first element from the list. Step 1. Get the delete positionFigure 17. Removing the first element from the list. Step 1. Save the value of the beginning of the list (begin)

C++. Linear doubly linked list. Removing the first element from the list. Step 2. Offset of the index of the beginning of the listFigure 18. Removing the first element from the list. Step 2. Move the begin pointer to the next element

C++. Linear doubly linked list. Removing the first element from the list. Step 3. Setting up the pointerFigure 19. Removing the first element from the list. Step 3. Setting the pointer prev of the beginning of the list (begin) to zero

C++. Linear doubly linked list. Removing the first element from the list. Step 4: Remove an elementFigure 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).

C++. Linear doubly linked list. Removing an element from the list. Step 1: Get the remove element and neighbor elementsFigure 21. Removing the element from the list. Step 1: Get the element to be removed and the previous and next elements

C++. Linear doubly linked list. Removing an element from the list. Step 2. Adjusting the pointers of neighboring partsFigure 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

C++. Linear doubly linked list. Removing an element from the list. Step 3: Remove an elementFigure 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.

C++. Linear doubly linked list. Remove the last element from the list. Step 1. Get the address of the last elementFigure 24. Remove the last element from the list. Remember the address of the last element

C++. Linear doubly linked list. Remove the last element from the list. Step 2. Move the pointer to the previous elementFigure 25. Removing the last item from the list. Move the end pointer to the previous element of the list

C++. Linear doubly linked list. Remove the last element from the list. Step 3. Destroying the elementFigure 26. Remove the last element from the list. Freeing the memory allocated for the last element

C++. Linear doubly linked list. Remove the last element from the list. Step 4. Setting the end of the list pointerFigure 27. Remove the last element from the list. Setting the next pointer to the last element of the list to zero

 


Related topics