Linear singly linked list. General information. Basic operations on the list
Contents
- 1. The concept of a singly linked list. Encoding features. Basic operations on the list
- 2. General view of the list. A structure describing a single element of the list
- 3. List formation
- 4. Inserting an element at a given position in a list
- 5. Removing an element from a list at a given position
- Related topics
Search other resources:
1. The concept of a singly linked list. Encoding features. Basic operations on the list
A singly linked list is a dynamic data structure that implements the formation and processing of a set of elements. The elements of a singly linked list may or may not be sorted.
A singly linked list can be stored:
- in RAM;
- in file.
In a singly linked list, a single element (Element) is distinguished, which is called a node (Node). Each element (node) of a singly linked list has two parts:
- data. It can be a variable of any primitive type (int, double, char, …), a class object, or a complex structure. Data can consist of several fields (variables);
- the address or position of the next element. If a singly linked list is stored in RAM, then this is a pointer (address) to the same element (node). If a singly linked list is stored in a file, then this is the position of the next element in the file.
You can implement a node using a class or structure. It is also possible to create a singly linked list based on a template class that operates on some generic type T.
The set of elements (nodes) in which the pointer of the previous element points to the next element forms a singly linked list.
The following main operations can be distinguished for the list:
- formation of the list;
- adding an element to the end of the list;
- inserting an element at a given position in the list;
- removal of an element from the list from the given position;
- clearing the list;
- replacing an element in the list;
- search for an element in the list by index or some criterion.
If desired, the list of operations can be expanded by adding your own ideas (for example, inserting a group of elements into a list, sorting elements in a list, creating a sorted list, etc.).
⇑
2. General view of the list. A structure describing a single element of the list
The general view of a linear singly linked list is shown in Figure 1.
Figure 1. General view of the list
Figure 2 shows the Element structure used as the base element of a linear singly linked list. Each element stores data of some type T.
Figure 2. An Element structure that describes a single element of a C++ list
⇑
3. List formation
3.1. Create empty list
Creating a list includes the following steps.
1. Declaring pointers to the beginning and end of the list.
2. Setting zero values to pointers.
3. Set the number of elements to 0.
Figure 3. List formation: 1) declaration of pointers; 2) setting zero values
⇑
3.2. Adding an element to the end of a list
When adding an element to the end of the list, 2 possible situations are considered:
- adding an element to an empty list;
- adding an element to a non-empty list (a list that has elements).
⇑
3.2.1. Adding a new element to the end of an empty list
When adding an element to the end of an empty list, the following operations are distinguished (Figure 4):
1. Create a new element. Here you need to allocate memory for a new element and fill it with some data (_data). To do this, a pointer is declared (for example, elem):
Element<T>* elem = new Element<T>; elem->data = _data;
2. Set next pointer to zero
elem->next = nullptr;
3. Set the begin and end pointers to the value of the elem pointer.
begin = end = elem;
4. Increase the number of elements in the list by 1
count++;
Figure 4. Adding an element to the end of the empty list: 1 – creating the element; 2 – setting the next pointer; 3 – setting the begin and end pointers
⇑
3.2.2. Adding an element to the end of an existing list
If the list already exists, then the sequence of steps to add an element to the list is as follows (Figure 5):
1. Create a new element and fill it with data (Figure 5). The fields data and next are filled. The creation of an element is carried out in the same way as in the case of an empty list:
Element<T>* elem = new Element<T>; elem->data = _data; elem->next = nullptr;
2. Set the next pointer of the element pointed to by the end pointer to the value of the address of the elem element (Figure 6)
end->next = elem;
3. Set the end pointer to the value of the elem pointer
end = elem;
4. Increase the number of elements in the list by 1
count++;
The above steps are more eloquently displayed in Figures 5, 6, 7.
Figure 5. Creating an element and filling it with data
Figure 6. Changing the next pointer of the end element
Figure 7. Setting the end pointer to the last element of the list
⇑
4. Inserting an element at a given position in a list
When inserting an element at a given position in the list, 2 options are considered:
- list is empty (no items);
- the list has at least one element.
If the list is empty, then the insertion is replaced by the addition of the first element, as described in paragraph 3.2.1.
If there are elements in the list, then 3 options are considered here:
- inserting an element at the first position of the list;
- inserting an element inside a list;
- inserting an element after the last element of the list. If an insertion occurs after the last element of the list, then this is the addition of an element to the end of the list as described in paragraph 3.2.2.
⇑
4.1. The list is not empty. Inserting an element at the first position of a list
If an element is inserted at the first position of the list, then the sequence of operations is as follows:
1. Create a new element (Figure 8). Allocate memory for the new element. Fill element with data.
// Allocating memory for a new cell Element<T>* elem = new Element<T>; elem->data = _data;
2. Set the next element pointer to the beginning of the list (Figure 9).
elem->next = begin;
3. Set the beginning of the list to a new cell (Figure 10).
begin = elem;
All of the above steps are graphically shown in Figures 8, 9, 10.
Figure 8. Creating a new element. Filling element fields with values
Figure 9. Insert an element at the beginning of the list. Setting the next field to the address of the first element in the list
Figure 10. Assigning the pointer to the beginning of the list the address of the newly created element
⇑
4.2. The list is not empty. Insert an element in the middle of the list
If the element is inserted before the second, third, etc. as well as the last position of the list, then the following steps are performed.
1. Create element. Fill in the element’s data field
Element<T>* elem = new Element<T>; elem->data = _data;
2. Determine the position of the element that comes before the insertion position of the element. Get a pointer to this position.
Element<T>* elemPrev = Move(index - 1);
where Move() is a method that returns the position of the element before the insertion position index.
3. Set the next pointer of the elem to be inserted
elem->next = elemPrev->next;
4. Set the next pointer of the previous elemPrev to point to the elem to be inserted
elemPrev->next = elem;
The previous 4 steps are shown in figures 11, 12, 13, 14.
Figure 11. Create an element. Filling an Element with data
Figure 12. Inserting an element into a list. Search for the element that comes before the insertion position
Figure 13. Insert an element into the list. Setting the next pointer of the inserted element
Figure 14. Inserting an element into a list. Set the next pointer to the element before the insertion position
⇑
5. Removing an element from a list at a given position
To remove an element from a list, it first checks to see if the list is empty. If the list is not empty (the list contains at least one element), then the element is removed.
When removing an element from a list, 2 possible situations are considered:
- the first element is removed from the list;
- not the first element is removed from the list (second, third, etc.).
⇑
5.1. The list is not empty. Deleting the first element from a list
If the first element in the list is removed, then the sequence of removal steps is as follows.
1. Get the address of the first element (Figure 15)
Element<T>* delElem = begin;
2. Move the pointer to the beginning of the begin list to the next element
begin = begin->next;
3. Release the memory allocated for the delElem element
delete delElem;
Figures 15, 16, 17 show the entire process of removing the first element from the list.
Figure 15. Removing the first element from the list. Step 1. Create a pointer to the first element
Figure 16. Removing an element. Step 2. Move the pointer to the beginning of the list to the next element
Figure 17. Deleting an element. Step 3. Release the memory allocated for the element
⇑
5.2. The list is not empty. Deleting non-first element from a list
If not the first element (second, third, etc., last) is removed from a non-empty list, then the sequence of steps is as follows.
1. Move the pointer to the position before the element to be removed. Get the element preceding the element to be removed
Element<T>* elemPrev = Move(index - 1);
where Move() is a method that returns an element at a specified position.
2. Save the deleted element
Element<T>* elemDel = elemPrev->next;
3. Shift the next pointer of the previous elemPrev element to bypass the elemDel element being removed
elemPrev->next = elemDel->next;
4. Delete the element elemDel (free the memory allocated for the element).
delete elemDel;
Figures 18, 19, 20, 21 show the above steps schematically.
Figure 18. Removing an element from the middle of the list. Move to the next element before the previous one
Figure 19. Removing an element. Get the element to be removed
Figure 20. Deleting an element from the list. Offset of the next pointer of the previous element, bypassing the element being removed
Figure 21. Deleting the element from the list. Deallocation of memory occupied by the element
⇑
Related topics
- An example of implementation of a linear singly-linked list for the generic type T
- Linear doubly linked list. General concepts. Basic operations on the list
- Linear doubly linked list. Example of a template class
⇑