From Basic to Intermediate: Queues, Lists, and Trees (IV)

Introduction

In the previous article From Basic to Intermediate: Queues, Lists, and Trees (III), we covered the basics of what a linked list is. We also saw that with a simple change to the code, we could create a doubly linked list or a singly linked list. This is something that many people consider difficult. However, the material covered in the previous article does not demonstrate all the capabilities that a linked list offers. Nor does it explain why, in many cases, this is the best option when you need to implement a system that needs to process large volumes of data.

It is important to remember that this data was originally stored in arrays. However, using arrays can make our code quite be expensive at runtime. To address this specific issue, researchers in data science developed the mechanism explained in these articles. Keep in mind that I try to explain things here as simply and clearly as possible.

So, the mechanism described so far only allows us to insert and delete values located at the ends of a linked list. However, we often have to add and remove values at positions in the middle of the list. This is precisely the mechanism that remains unexplained, since that part has not yet been implemented. All right, let's continue our ritual of eliminating any distractions that might prevent you from focusing on what we will cover in this article. Let's start implementing the final part so that the linked list becomes fully functional. As usual, we will move on to a new topic to begin our journey through the fascinating world of programming.

Queues, Lists, and Trees (IV)

In the previous article, we ended with the code shown below:

01. //+------------------------------------------------------------------+
02. #property copyright "Daniel Jose"
03. //+------------------------------------------------------------------+
04. template <typename T> class stList
05. {
06.     private:
07. //+----------------+
08.         T info;
09.         stList <T>  *prev,
10.                     *start;
11. //+----------------+
12.     public:
13. //+----------------+
14.         stList(void)
15.             :prev(NULL),
16.             start(NULL)
17.         {}
18. //+----------------+
19.         void Store(T arg, const ENUM_FILE_POSITION pos = SEEK_END)
20.         {
21.             stList <T> *loc;
22. 
23.             loc = new stList <T>;
24. 
25.             (*loc).info = arg;
26.             (*loc).prev = NULL;
27.             switch(pos)
28.             {
29.                 case SEEK_SET:
30.                     (*loc).start = start;
31.                     (*start).prev = loc;
32.                     start = loc;
33.                     break;
34.                 case SEEK_END:
35.                     if (prev != NULL) (*prev).start = loc;
36.                     (*loc).prev = prev;
37.                     prev = loc;
38.                     start = (start == NULL ? loc : start);
39.                     break;
40.             }
41.         }
42. //+----------------+
43.         bool Restore(T &arg, const ENUM_FILE_POSITION pos = SEEK_END)
44.         {
45.             stList <T> *loc = NULL;
46. 
47.             if ((prev == NULL) || (start == NULL))
48.                 return false;
49. 
50.             switch (pos)
51.             {
52.                 case SEEK_SET:
53.                     loc = start;
54.                     start = (*loc).start;
55.                     break;
56.                 case SEEK_END:
57.                     loc = prev;
58.                     prev = (*loc).prev;
59.                     break;
60.             }
61.             arg = (*loc).info;
62. 
63.             delete loc;
64. 
65.             return true;
66.         }
67. //+----------------+
68.         void Debug(void)
69.         {
70.             Print("===== DEBUG =====");
71.             for (stList <T> *loc = prev; loc != NULL; loc = (*loc).prev)
72.                 PrintFormat("0x%06X ->> 0x%06X <<- 0x%06X = [%d]",(*loc).start, loc, (*loc).prev, (*loc).info);
73.             Print("=================");
74.         }
75. //+----------------+
76. };
77. //+------------------------------------------------------------------+
78. void OnStart(void)
79. {
80.     stList <char> list;
81. 
82.     list.Store(10);
83.     list.Store(84);
84.     list.Store(-6);
85.     list.Store(47, SEEK_SET);
86. 
87.     list.Debug();
88. 
89.     for (char info; list.Restore(info, SEEK_SET);)
90.         Print(info);
91. };
92. //+------------------------------------------------------------------+

Code 01

This code lets us create a list that behaves like a stack, or a list that operates on the FIFO (first in, first out) principle. Everything is presented in a very simple way. For more detailed information, please refer to the previous article. However, although this capability already makes Code 01 quite useful for solving various problems, it lacks a mechanism for inserting or removing list elements that are not at either end of the list. In other words: Code 01 allows us to remove or add only the first or last element of the list, but never a middle element.

Nevertheless, in the previous article I suggested that you solve this problem. The idea was to let you check how well you understood the explanations and examples provided in the article. If you managed to do that, congratulations. Even though I gave a few tips, it is still not that easy for beginners. This is because it is necessary to consider how to handle certain details of the code being implemented.

In any case, whether or not you were able to solve the problem presented in the previous article, here we will consider my proposed solution. Remember that the purpose is educational. So, let's get started.

To start, let's analyze the result of running Code 01. The result is shown below.

Figure 01

The idea is to first remove one of these values. In this case, the value 84 or the value 10, without significantly changing Code 01 and without copying the list shown in Figure 01 to another memory location. The easiest way to do this is to modify the list’s own prev and start pointers so as to remove the desired element. That is the main idea. But how do you do that? If you look at Figure 01, you will notice that the section where we are debugging the list shows how the addresses are linked. Suppose we want to remove the element whose value is 84.

If you look at Figure 01, you will see that the address of this element is 0x300000; note the middle column. The previous address is 0x200000, and the next one is 0x400000. Based on this information, we can determine how to remove the element with the value 84: to do this, we need the previous element, 10, to point to the next element, -6, and the element with the value -6 to point to 10. Therefore, the element with the value 84 can be safely removed from the list.

I think you now know what we need to do. To show you how this works in practice, let's take a look at the code below, which removes this exact element, 84:

001. //+------------------------------------------------------------------+
002. #property copyright "Daniel Jose"
003. //+------------------------------------------------------------------+
004. template <typename T> class stList
005. {
006.     private:
007. //+----------------+
008.         T info;
009.         stList <T>  *prev,
010.                     *start;
011. //+----------------+
012.     public:
013. //+----------------+
014.         stList(void)
015.             :prev(NULL),
016.             start(NULL)
017.         {}
018. //+----------------+
019.         void Store(T arg, const ENUM_FILE_POSITION pos = SEEK_END)
020.         {
021.             stList <T> *loc;
022. 
023.             loc = new stList <T>;
024. 
025.             (*loc).info = arg;
026.             (*loc).prev = NULL;
027.             switch(pos)
028.             {
029.                 case SEEK_SET:
030.                     (*loc).start = start;
031.                     (*start).prev = loc;
032.                     start = loc;
033.                     break;
034.                 case SEEK_END:
035.                     if (prev != NULL) (*prev).start = loc;
036.                     (*loc).prev = prev;
037.                     prev = loc;
038.                     start = (start == NULL ? loc : start);
039.                     break;
040.             }
041.         }
042. //+----------------+
043.         bool Restore(T &arg, const ENUM_FILE_POSITION pos = SEEK_END)
044.         {
045.             stList <T> *loc = NULL;
046. 
047.             if ((prev == NULL) || (start == NULL))
048.                 return false;
049. 
050.             switch (pos)
051.             {
052.                 case SEEK_SET:
053.                     loc = start;
054.                     start = (*loc).start;
055.                     break;
056.                 case SEEK_END:
057.                     loc = prev;
058.                     prev = (*loc).prev;
059.                     break;
060.             }
061.             arg = (*loc).info;
062. 
063.             delete loc;
064. 
065.             return true;
066.         }
067. //+----------------+
068.         bool Exclude(const T arg)
069.         {
070.             stList <T>  *loc = start,
071.                         *ptr = NULL;
072. 
073.             for (; loc != NULL; ptr = loc, loc = (*loc).start)
074.                 if ((*loc).info == arg) break;
075. 
076.             if (loc == NULL) return false;
077. 
078.             (*ptr).start = (*loc).start;
079.             (*loc).start.prev = ptr;
080.             
081.             delete loc;
082. 
083.             return true;
084.         }
085. //+----------------+
086.         void Debug(void)
087.         {
088.             Print("===== DEBUG =====");
089.             for (stList <T> *loc = prev; loc != NULL; loc = (*loc).prev)
090.                 PrintFormat("0x%06X ->> 0x%06X <<- 0x%06X = [%d]",(*loc).start, loc, (*loc).prev, (*loc).info);
091.             Print("=================");
092.         }
093. //+----------------+
094. };
095. //+------------------------------------------------------------------+
096. void OnStart(void)
097. {
098.     stList <char> list;
099. 
100.     list.Store(10);
101.     list.Store(84);
102.     list.Store(-6);
103.     list.Store(47, SEEK_SET);
104. 
105.     list.Debug();
106.     list.Exclude(84);
107.     list.Debug();
108. 
109.     for (char info; list.Restore(info, SEEK_SET);)
110.         Print(info);
111. };
112. //+------------------------------------------------------------------+

Code 02

Now, pay attention. Code 02 implements exactly what was explained just a moment ago. In other words, when line 106 is executed, a function is called that removes the element with the value 84. Before we take a detailed look at how the function on line 68 works, let's examine the execution of Code 02. The result is shown below.

Figure 02

Figure 02 shows quite clearly what is happening. If you look at the values that were printed by line 105, you will notice that when line 107 is executed, the addresses of elements -6 and 10 change. Thus, the element with the value 84 is no longer part of the list. But wait, where did the element with the value 84 go? Well, dear reader, that element has been removed. Now let's consider the code that does exactly that, so you will understand everything.

To make the explanation as simple as possible and avoid confusion between a linked list and anything else, we will initially work only with the values of the elements. Thus, the function on line 68 will receive the value of the element we want to remove from the linked list. Since we do not know where this element is in the list—it could be anywhere—we initialize some auxiliary variables on lines 70 and 71. Now let's start searching for an element in the list. The search is performed in a loop on line 73. When the element is found, line 74 will terminate the loop.

It is also possible that the element will not be found. In this case, the loop will end when there are no more elements left in the list. For this reason, we need line 76 to check whether we have reached the end of the list or found the element that must be deleted. If we find the element that we want to remove, we execute the following lines of code. Otherwise, the deletion function will terminate.

So, let's move on to the part that confuses a lot of people. Since the element has a previous and a next node, we must directly link the previous node to the next one. This is the only way we can delete the found element. To establish this connection, we need lines 78 and 79. Once the connection has been established, the element can be deleted. The deletion occurs on line 81. As a result, the linked list continues to work flawlessly, as if nothing had changed.

That said, that was the easiest part. Try to get a very good understanding of what has been explained so far, because next comes the part that makes many people want to send the creators or implementers of the linked list concept straight to hell. That is how much confusion many people create around what we are about to see next.

First, it is not very practical to specify exactly which value should be removed from the linked list. Although we can use this approach in some cases, in practice it is not used very often. Many programmers implement this mechanism in a different way.

In my previous article, I explained that a linked list can be thought of as an array, and I also explained why linked lists came about. Since a linked list can be thought of as an array, it is most practical to specify the index of the element we want to remove. Imagine the following situation: you can work with any set of values, and although you do not know which value to remove, you most likely know where it is. Wouldn't it be much more practical to specify the index of the desired value? In fact, dear reader, that is exactly the case. However, there is a small problem. And it is already visible in the code shown.

To illustrate this, let's use code 02 as an example. Please note the following: on line 100, we start our list with the value 10; then we insert the value 84, followed by the value -6. However, the value 47 was placed before the element with the value 10. As we will see later, many other values could be inserted at any position in the list. But for now, let's focus on these values and this issue. Question: At which position is the value 84? If you look closely, you will see that it is at index 2. Remember that numbering starts at zero. However, if you look at the code without understanding it, you might think that the value 84 is at index one. This is because it is added after the element with a value of 10, but that would be true if it were not for line 103, where we add the element with a value of 47 BEFORE the element with a value of 10. It is exactly these kinds of things that cause a lot of confusion among many beginners.

There is also a second problem, which is less complicated. Depending on how you traverse the linked list, you might end up deleting the wrong element. This happens when the list is traversed from the end to the beginning. For this reason, special care must be taken when determining the first and last elements. This may seem silly, but if you ever create a circular linked list, this kind of situation can make the implementation really confusing. Although circular linked lists are not very common precisely because of the confusion surrounding the definition of the first element, you may need to create one. And if that happens, be careful when implementing the code.

Now we know about some of the dangers we are going to face. We also already know how to visualize a linked list to see how similar it is to an array. So, let's move on to the most interesting part: implementing the code that will use indexes instead of values. The corresponding code is shown below:

001. //+------------------------------------------------------------------+
002. #property copyright "Daniel Jose"
003. //+------------------------------------------------------------------+
004. template <typename T> class stList
005. {
006.     private:
007. //+----------------+
008.         T info;
009.         stList <T>  *prev,
010.                     *start;
011.         uint        counter;
012. //+----------------+
013.         bool RemoveNode(stList <T> *arg)
014.         {
015.             delete arg;
016.             counter--;
017. 
018.             return true;
019.         }
020. //+----------------+
021.     public:
022. //+----------------+
023.         stList(void)
024.             :prev(NULL),
025.             start(NULL),
026.             counter(0)
027.         {}
028. //+----------------+
029.         void Store(T arg, const ENUM_FILE_POSITION pos = SEEK_END, const uint index = 0)
030.         {
031.             stList <T> *loc;
032. 
033.             loc = new stList <T>;
034. 
035.             (*loc).info = arg;
036.             (*loc).prev = NULL;
037.             switch(pos)
038.             {
039.                 case SEEK_SET:
040.                     (*loc).start = start;
041.                     (*start).prev = loc;
042.                     start = loc;
043.                     break;
044.                 case SEEK_CUR:
045.                     break;
046.                 case SEEK_END:
047.                     if (prev != NULL) (*prev).start = loc;
048.                     (*loc).prev = prev;
049.                     prev = loc;
050.                     start = (start == NULL ? loc : start);
051.                     break;
052.             }
053.             counter++;
054.         }
055. //+----------------+
056.         bool Restore(T &arg, const ENUM_FILE_POSITION pos = SEEK_END)
057.         {
058.             stList <T> *loc = NULL;
059. 
060.             if ((prev == NULL) || (start == NULL))
061.                 return false;
062. 
063.             switch (pos)
064.             {
065.                 case SEEK_SET:
066.                     loc = start;
067.                     start = (*loc).start;
068.                     if (start != NULL)
069.                         (*start).prev = NULL;
070.                     break;
071.                 case SEEK_END:
072.                     loc = prev;
073.                     prev = (*loc).prev;
074.                     if (prev != NULL)
075.                         (*prev).start = NULL;
076.                     break;
077.             }
078.             arg = (*loc).info;
079. 
080.             return RemoveNode(loc);
081.         }
082. //+----------------+
083.         bool Exclude(const uint index)
084.         {
085.             T arg;
086.             ENUM_FILE_POSITION pos = (index == 0 ? SEEK_SET : (index >= counter ? SEEK_END : SEEK_CUR));
087. 
088.             if (pos == SEEK_CUR)
089.             {
090.                 stList <T>  *loc = start,
091.                             *ptr = NULL;
092. 
093.                 for (uint c = 0; (loc != NULL) && (c < index); ptr = loc, loc = (*loc).start, c++);
094.                 if (loc == NULL) return false;
095. 
096.                 (*ptr).start = (*loc).start;
097.                 (*loc).start.prev = ptr;
098. 
099.                 return RemoveNode(loc);
100.             }
101. 
102.             return Restore(arg, pos);
103.         }
104. //+----------------+
105.         void Debug(void)
106.         {
107.             Print("===== DEBUG =====");
108.             for (stList <T> *loc = start; loc != NULL; loc = (*loc).start)
109.                 PrintFormat("0x%06X ->> 0x%06X <<- 0x%06X = [%d]", (*loc).start, loc, (*loc).prev, (*loc).info);
110.             Print("=================");
111.         }
112. //+----------------+
113. };
114. //+------------------------------------------------------------------+
115. void OnStart(void)
116. {
117.     stList <char> list;
118. 
119.     list.Store(10);
120.     list.Store(84);
121.     list.Store(-6);
122.     list.Store(47, SEEK_SET);
123. 
124.     list.Debug();
125. 
126.     list.Exclude(2);
127. 
128.     list.Debug();
129. 
130.     for (char info; list.Restore(info, SEEK_SET);)
131.         Print(info);
132. };
133. //+------------------------------------------------------------------+

Code 03

"Are you kidding? What kind of crazy code is this?" Maybe I exaggerated a little by presenting it this way. (LAUGHTER). This code is not all that crazy. To be honest, it is very easy to understand, even though it is not the prettiest one. Let's take a look at what this code does. First, I added a new variable on line 11. This variable indicates the number of elements in the list. This is similar to using the ArraySize function to determine the number of elements in a dynamic array.

Since this number may change when elements are added or removed, lines 16 and 53 are responsible for adjusting it. Note that on line 44 of Code 03, I have already left room for a new option that will be implemented soon. But let's focus on the part responsible for removing elements. Note that the Exclude function on line 83 now takes a value that specifies which element should be removed from the list. This is determined based on the element's position in the list.

Now pay close attention, dear reader, because this part is quite interesting: reading list elements is a destructive operation. In other words, when reading the list in any order, the element being read is removed. We can take advantage of this. When the resulting index is zero, we can use the Restore function itself from line 56 to remove the first element of the list. The same applies to removing the last element from the list. To do this, we use line 86, which indicates whether the element being removed is the first, the last, or one somewhere in the middle.

If the element to be removed is in a position in the middle of the list, the check on line 88 will be performed, and we can do something similar to what was done in Code 02. Unlike what was done in Code 02, the check in Code 03 that we use to find the element to be deleted is different. In this case, it is enough to look at the loop on line 93 and compare it with the loop in Code 02. You will see that here we use a counter to find the element that will be deleted. We do not know exactly where it is. All we know is which index we should use. The rest of the code is virtually identical to Code 02.

Thus, when line 126 is executed, Code 03 will produce the same result that we saw when running Code 02. In other words, Figure 02. Code 03 is very interesting, but we can do something a little differently. Before showing what the code for inserting elements into the list will look like, let's run an experiment with Code 03. The experiment is shown below:

001. //+------------------------------------------------------------------+
002. #property copyright "Daniel Jose"
003. //+------------------------------------------------------------------+
004. template <typename T> class stList
005. {
006.     private:
007. //+----------------+
008.         T info;
009.         stList <T>  *prev,
010.                     *start;
011.         uint        counter;
012. //+----------------+
013.         bool RemoveNode(stList <T> *arg)
014.         {
015.             delete arg;
016.             counter--;
017. 
018.             return true;
019.         }
020. //+----------------+
021.     public:
022. //+----------------+
023.         stList(void)
024.             :prev(NULL),
025.             start(NULL),
026.             counter(0)
027.         {}
028. //+----------------+
029.         void Store(T arg, const ENUM_FILE_POSITION pos = SEEK_END, const uint index = 0)
030.         {
031.             stList <T> *loc;
032. 
033.             loc = new stList <T>;
034. 
035.             (*loc).info = arg;
036.             (*loc).prev = NULL;
037.             switch(pos)
038.             {
039.                 case SEEK_SET:
040.                     (*loc).start = start;
041.                     (*start).prev = loc;
042.                     start = loc;
043.                     break;
044.                 case SEEK_CUR:
045.                     break;
046.                 case SEEK_END:
047.                     if (prev != NULL) (*prev).start = loc;
048.                     (*loc).prev = prev;
049.                     prev = loc;
050.                     start = (start == NULL ? loc : start);
051.                     break;
052.             }
053.             counter++;
054.         }
055. //+----------------+
056.         bool Restore(T &arg, const ENUM_FILE_POSITION pos = SEEK_END)
057.         {
058.             stList <T> *loc = NULL;
059. 
060.             if ((prev == NULL) || (start == NULL))
061.                 return false;
062. 
063.             switch (pos)
064.             {
065.                 case SEEK_SET:
066.                     loc = start;
067.                     start = (*loc).start;
068.                     if (start != NULL)
069.                         (*start).prev = NULL;
070.                     break;
071.                 case SEEK_END:
072.                     loc = prev;
073.                     prev = (*loc).prev;
074.                     if (prev != NULL)
075.                         (*prev).start = NULL;
076.                     break;
077.             }
078.             arg = (*loc).info;
079. 
080.             return RemoveNode(loc);
081.         }
082. //+----------------+
083.         bool Exclude(const int arg)
084.         {
085.             T tmp;
086.             uint index = MathAbs(arg);
087.             ENUM_FILE_POSITION pos = (index == 0 ? SEEK_SET : (index >= counter ? SEEK_END : SEEK_CUR));
088. 
089.             if (pos == SEEK_CUR)
090.             {
091.                 stList <T>  *loc = (arg < 0 ? prev : start),
092.                             *ptr = NULL;
093. 
094.                 for (uint c = 0; (loc != NULL) && (c < index); ptr = loc, loc = (arg < 0 ? (*loc).prev : (*loc).start), c++);
095.                 if (loc == NULL) return false;
096. 
097.                 if (arg < 0)
098.                 {
099.                     (*ptr).prev = (*loc).prev;
100.                     (*loc).prev.start = ptr;
101.                 }else{
102.                     (*ptr).start = (*loc).start;
103.                     (*loc).start.prev = ptr;
104.                 }
105. 
106.                 return RemoveNode(loc);
107.             }
108. 
109.             return Restore(tmp, pos);
110.         }
111. //+----------------+
112.         void Debug(void)
113.         {
114.             Print("===== DEBUG =====");
115.             for (stList <T> *loc = start; loc != NULL; loc = (*loc).start)
116.                 PrintFormat("0x%06X ->> 0x%06X <<- 0x%06X = [%d]", (*loc).start, loc, (*loc).prev, (*loc).info);
117.             Print("=================");
118.         }
119. //+----------------+
120. };
121. //+------------------------------------------------------------------+
122. void OnStart(void)
123. {
124.     stList <char> list;
125. 
126.     list.Store(10);
127.     list.Store(84);
128.     list.Store(-6);
129.     list.Store(47, SEEK_SET);
130. 
131.     list.Debug();
132. 
133.     list.Exclude(-2);
134. 
135.     list.Debug();
136. 
137.     for (char info; list.Restore(info, SEEK_SET);)
138.         Print(info);
139. };
140. //+------------------------------------------------------------------+

Code 04

The experiment involved changing the type of argument that the Exclude function can accept. Note that, unlike in Code 03, in Code 04 we can pass both positive and negative values to the Exclude function. But what does that mean in practice? This means we can remove elements from both the beginning and the end of the list. "Well, you really do not give us a break. I had barely started to understand the code when you came along and made it even more complicated. Don't you ever get tired?" Not at all, dear reader. I find what we can do very amusing. And the more tangled this mechanism becomes, the more I enjoy writing the code.

Despite this apparent confusion, you will easily understand what is going on. Note that the only thing that had to be changed in Code 04 is how the search loop works. We also needed to make a small adjustment because we can traverse the list starting from either the beginning or the end.

How can we control this? Dear reader, this part is the simplest. If the value of the argument of the Exclude function is positive, we will proceed in the same way as in code 03. If the value is negative, the traversal will be interpreted differently. First, we always need to convert the value to a positive number, which will help avoid problems. To do this, we use line 86 to get the correct value, regardless of whether it is positive or negative. If the loop on line 94 is executed, we change the direction of traversal. That is, if the value is negative, it will always point to the previous element. If the value is positive, we will move to the next element. In any case, there will be a reference to an element here. And now it is time to adjust the pointers correctly.

Since we can traverse the list from the end to the beginning, the pointer updates may need to be reversed. For this reason, on line 97, we check the direction in which the list is being traversed. If we traverse it in the opposite direction—that is, from the end to the beginning—we need to use lines 99 and 100 to adjust the pointers correctly. Ultimately, the result will always be correct if you pay close attention.

To illustrate this, note that on line 133, we pass a negative value as an argument to the Exclude function. Therefore, the element with index two, counting from the end of the list, will be removed. If you have understood everything we have been doing from the very beginning, you will know that this element has the value 10, so when you run code 04, the result will be as shown in the following Figure.

Figure 03

All right, enough joking around. It is time to implement the part responsible for inserting values at arbitrary positions in the list. It is similar to what we just did with the delete method. As you can probably imagine, we will not just implement this haphazardly; instead, we will experiment with the code as we develop it. This will help you better understand how the mechanism works and why it is implemented this way.

So, let's focus on Code 04, which is responsible for inserting values in the list. If you look at the `switch` statement on line 37, you will see that a series of steps is performed to insert a new element at the end or at the beginning of the list. These steps are specifically intended to set the memory addresses of the previous and next elements relative to the new element we are adding. It is very important that you pay attention to how this is done. In fact, the difference between inserting a new element at the beginning or at the end of the list is which pointer will point to the new element. But why does this happen? So, if you look at the `case` branch on line 39, you will see that we are adding a new element to the front of the queue. The reason is given on line 42.

If you look at line 46, you will see that we are adding an element to the end of the queue. This is done in line 49. Now the question arises. When we specify an index, the logic changes, because in that case we are specifying where the element will be inserted. But at this stage, we need to take a moment to think through this mechanism. And the reason, in a sense, is directly related to what we observed when removing elements from the list.

To avoid complicating the insertion mechanism, let's do the following: insert a new element using the beginning of the list as the starting point. The following code shows what we need to do:

001. //+------------------------------------------------------------------+
002. #property copyright "Daniel Jose"
003. //+------------------------------------------------------------------+
004. template <typename T> class stList
005. {
006.     private:
007. //+----------------+
008.         T info;
009.         stList <T>  *prev,
010.                     *start;
011.         uint        counter;
012. //+----------------+
013.         bool RemoveNode(stList <T> *arg)
014.         {
015.             delete arg;
016.             counter--;
017. 
018.             return true;
019.         }
020. //+----------------+
021.     public:
022. //+----------------+
023.         stList(void)
024.             :prev(NULL),
025.             start(NULL),
026.             counter(0)
027.         {}
028. //+----------------+
029.         void Store(T arg, const ENUM_FILE_POSITION pos = SEEK_END, const uint index = 0)
030.         {
031.             stList <T> *loc;
032. 
033.             loc = new stList <T>;
034. 
035.             (*loc).info = arg;
036.             (*loc).prev = NULL;
037.             switch(pos)
038.             {
039.                 case SEEK_SET:
040.                     (*loc).start = start;
041.                     (*start).prev = loc;
042.                     start = loc;
043.                     break;
044.                 case SEEK_CUR:
045.                     {
046.                         stList <T>  *ptr1 = start,
047.                                     *ptr2 = NULL;
048. 
049.                         for (uint c = 0; (ptr1 != NULL) && (c < index); ptr2 = ptr1, ptr1 = (*ptr1).start, c++);
050. 
051.                         (*loc).start = (ptr2 != NULL ? (*ptr2).start : ptr1);
052.                         (*loc).prev = (ptr1 != NULL ? (*ptr1).prev : ptr2);
053.                         if (ptr2 != NULL) (*ptr2).start = loc; else start = loc;
054.                         if (ptr1 != NULL) (*ptr1).prev = loc; else prev = loc;
055.                     }
056.                     break;
057.                 case SEEK_END:
058.                     if (prev != NULL) (*prev).start = loc;
059.                     (*loc).prev = prev;
060.                     prev = loc;
061.                     start = (start == NULL ? loc : start);
062.                     break;
063.             }
064.             counter++;
065.         }
066. //+----------------+
067.         bool Restore(T &arg, const ENUM_FILE_POSITION pos = SEEK_END)
068.         {
069.             stList <T> *loc = NULL;
070. 
071.             if ((prev == NULL) || (start == NULL))
072.                 return false;
073. 
074.             switch (pos)
075.             {
076.                 case SEEK_SET:
077.                     loc = start;
078.                     start = (*loc).start;
079.                     if (start != NULL)
080.                         (*start).prev = NULL;
081.                     break;
082.                 case SEEK_END:
083.                     loc = prev;
084.                     prev = (*loc).prev;
085.                     if (prev != NULL)
086.                         (*prev).start = NULL;
087.                     break;
088.             }
089.             arg = (*loc).info;
090. 
091.             return RemoveNode(loc);
092.         }
093. //+----------------+
094.         bool Exclude(const uint index)
095.         {
096.             T tmp;
097.             ENUM_FILE_POSITION pos = (index == 0 ? SEEK_SET : (index >= counter ? SEEK_END : SEEK_CUR));
098. 
099.             if (pos == SEEK_CUR)
100.             {
101.                 stList <T>  *loc = start,
102.                             *ptr = NULL;
103. 
104.                 for (uint c = 0; (loc != NULL) && (c < index); ptr = loc, loc = (*loc).start, c++);
105.                 if (loc == NULL) return false;
106. 
107.                 (*ptr).start = (*loc).start;
108.                 (*loc).start.prev = ptr;
109. 
110.                 return RemoveNode(loc);
111.             }
112. 
113.             return Restore(tmp, pos);
114.         }
115. //+----------------+
116.         void Debug(void)
117.         {
118.             Print("===== DEBUG =====");
119.             for (stList <T> *loc = start; loc != NULL; loc = (*loc).start)
120.                 PrintFormat("0x%06X ->> 0x%06X <<- 0x%06X = [%d]", (*loc).start, loc, (*loc).prev, (*loc).info);
121.             Print("=================");
122.         }
123. //+----------------+
124. };
125. //+------------------------------------------------------------------+
126. void OnStart(void)
127. {
128.     stList <char> list;
129. 
130.     list.Store(10);
131.     list.Store(84);
132.     list.Store(-6);
133.     list.Store(47, SEEK_SET);
134. 
135.     list.Debug();
136. 
137.     list.Store(35, SEEK_CUR, 2);
138. 
139.     list.Debug();
140. 
141.     for (char info; list.Restore(info, SEEK_SET);)
142.         Print(info);
143. };
144. //+------------------------------------------------------------------+

Code 05

Before explaining how Code 05 works, let's take a look at the result of its execution. This is shown in the following Figure:

Figure 04

So, in Figure 04, I show the result of inserting a value at a specific position in the list. Looking at Code 05, you might ask yourself, "How did you do that?" Since the goal here is to provide the clearest possible explanation, I've simplified Code 04. This can be seen in Code 05, in the section dealing with the deletion of values. However, what we're really interested in with this code is inserting values. For this reason, I want you to try to draw a parallel between the deletion code on line 94 and the insertion code between lines 44 and 56.

Let me emphasize this once again: the goal is to make the explanation as clear as possible. If you compare the deletion code with the insertion code, you will see that most of it is similar. Many people get confused at this point: the insertion code requires three pointers, while the deletion code requires only two. What is the reason for this difference? The reason is simple.

When adding a value to the list, we do not move any values, as we would when working with arrays. In the case of a linked list, it is simply a matter of setting the pointers so that they point to the previous or next element in the list. Thus, the code that actually inserts a new element into the list corresponds to lines 53 and 54. In other words, we use two if statements to set up the list correctly. To keep the list's structure intact, we use lines 51 and 52 to make the element being inserted point to the existing elements.

Now, pay attention: the lines of code I just mentioned allow you to create a doubly linked list without having to write code for the SEEK_SET and SEEK_END cases. In other words, this code within the SEEK_CUR case can insert elements at the beginning, at the end, or at an arbitrary position in the list. Just specify the index to be used.

"Hmm... Let me make sure I understand everything correctly. Are you saying that Code 05 can be modified to reduce its size? Nevertheless, this will work and produce the same result as in Figure 04, right?" Yes, dear reader. Code 05 was created so that you could understand how to implement this mechanism. This same Code 05 can be modified to obtain the result shown below:

001. //+------------------------------------------------------------------+
002. #property copyright "Daniel Jose"
003. //+------------------------------------------------------------------+
004. template <typename T> class stList
005. {
006.     private:
007. //+----------------+
008.         T info;
009.         stList <T>  *prev,
010.                     *start;
011.         uint        counter;
012. //+----------------+
013.         bool RemoveNode(stList <T> *arg)
014.         {
015.             delete arg;
016.             counter--;
017. 
018.             return true;
019.         }
020. //+----------------+
021.     public:
022. //+----------------+
023.         stList(void)
024.             :prev(NULL),
025.             start(NULL),
026.             counter(0)
027.         {}
028. //+----------------+
029.         void Store(T arg, const uint index = 0xFFFFFFFF)
030.         {
031.             stList <T> *loc,
032.                         *ptr1 = start,
033.                         *ptr2 = NULL;
034. 
035.             for (uint c = 0; (ptr1 != NULL) && (c < index); ptr2 = ptr1, ptr1 = (*ptr1).start, c++);
036. 
037.             loc = new stList <T>;
038.             (*loc).info = arg;
039.             (*loc).start = (ptr2 != NULL ? (*ptr2).start : ptr1);
040.             (*loc).prev = (ptr1 != NULL ? (*ptr1).prev : ptr2);
041.             if (ptr2 != NULL) (*ptr2).start = loc; else start = loc;
042.             if (ptr1 != NULL) (*ptr1).prev = loc; else prev = loc;
043. 
044.             counter++;
045.         }
046. //+----------------+
047.         bool Restore(T &arg, const ENUM_FILE_POSITION pos = SEEK_END)
048.         {
049.             stList <T> *loc = NULL;
050. 
051.             if ((prev == NULL) || (start == NULL))
052.                 return false;
053. 
054.             switch (pos)
055.             {
056.                 case SEEK_SET:
057.                     loc = start;
058.                     start = (*loc).start;
059.                     if (start != NULL)
060.                         (*start).prev = NULL;
061.                     break;
062.                 case SEEK_END:
063.                     loc = prev;
064.                     prev = (*loc).prev;
065.                     if (prev != NULL)
066.                         (*prev).start = NULL;
067.                     break;
068.             }
069.             arg = (*loc).info;
070. 
071.             return RemoveNode(loc);
072.         }
073. //+----------------+
074.         bool Exclude(const uint index)
075.         {
076.             T tmp;
077.             ENUM_FILE_POSITION pos = (index == 0 ? SEEK_SET : (index >= counter ? SEEK_END : SEEK_CUR));
078. 
079.             if (pos == SEEK_CUR)
080.             {
081.                 stList <T>  *loc = start,
082.                             *ptr = NULL;
083. 
084.                 for (uint c = 0; (loc != NULL) && (c < index); ptr = loc, loc = (*loc).start, c++);
085.                 if (loc == NULL) return false;
086. 
087.                 (*ptr).start = (*loc).start;
088.                 (*loc).start.prev = ptr;
089. 
090.                 return RemoveNode(loc);
091.             }
092. 
093.             return Restore(tmp, pos);
094.         }
095. //+----------------+
096.         void Debug(void)
097.         {
098.             Print("===== DEBUG =====");
099.             for (stList <T> *loc = start; loc != NULL; loc = (*loc).start)
100.                 PrintFormat("0x%06X ->> 0x%06X <<- 0x%06X = [%d]", (*loc).start, loc, (*loc).prev, (*loc).info);
101.             Print("=================");
102.         }
103. //+----------------+
104. };
105. //+------------------------------------------------------------------+
106. void OnStart(void)
107. {
108.     stList <char> list;
109. 
110.     list.Store(10);
111.     list.Store(84);
112.     list.Store(-6);
113.     list.Store(47, 0);
114. 
115.     list.Debug();
116. 
117.     list.Store(35, 2);
118. 
119.     list.Debug();
120. 
121.     for (char info; list.Restore(info, SEEK_SET);)
122.         Print(info);
123. };
124. //+------------------------------------------------------------------+

Code 06

Now, pay close attention to what I am going to explain. Otherwise, you will lose the thread and will not understand what we are going to do next. If you look at the procedure on line 29 of Code 06, you will see that it has changed, but only very slightly. Now this procedure will receive only the element that needs to be inserted, along with its index. To ensure that Code 06 continues to function the same way as Code 05 with regard to the contents of the OnStart procedure, the default index corresponds to the end of the list. In other words, if no value is specified as the element's position index, we will ALWAYS place the new element at the end of the list — or, if you prefer the stack analogy, at the top.

It is very important that you understand this, dear reader. Otherwise, you might try to implement the mechanism in one way, while the code actually performs it differently. To make this clearer, compare the OnStart procedure in Code 06 with the same procedure in Code 05. You will see that they are very similar.

In conclusion, let’s make a small adjustment to this same code 06. This will allow you to read an element from any position in the list. Keep in mind that when we perform this read operation, we will remove the value we have read from the list. But since the purpose here is educational, I do not see a problem with doing it this way. So, after applying the change, we will end up with the code shown below.

001. //+------------------------------------------------------------------+
002. #property copyright "Daniel Jose"
003. //+------------------------------------------------------------------+
004. template <typename T> class stList
005. {
006.     private:
007. //+----------------+
008.         T info;
009.         stList <T>  *prev,
010.                     *start;
011.         uint        counter;
012. //+----------------+
013.     public:
014. //+----------------+
015.         stList(void)
016.             :prev(NULL),
017.             start(NULL),
018.             counter(0)
019.         {}
020. //+----------------+
021.         void Store(T arg, const uint index = 0xFFFFFFFF)
022.         {
023.             stList <T> *loc,
024.                         *ptr1 = start,
025.                         *ptr2 = NULL;
026. 
027.             for (uint c = 0; (ptr1 != NULL) && (c < index); ptr2 = ptr1, ptr1 = (*ptr1).start, c++);
028. 
029.             loc = new stList <T>;
030.             (*loc).info = arg;
031.             (*loc).start = (ptr2 != NULL ? (*ptr2).start : ptr1);
032.             (*loc).prev = (ptr1 != NULL ? (*ptr1).prev : ptr2);
033.             if (ptr2 != NULL) (*ptr2).start = loc; else start = loc;
034.             if (ptr1 != NULL) (*ptr1).prev = loc; else prev = loc;
035. 
036.             counter++;
037.         }
038. //+----------------+
039.         bool Restore(T &arg, const uint index = 0xFFFFFFFF)
040.         {
041.             if ((prev == NULL) || (start == NULL))
042.                 return false;
043. 
044.             stList <T>  *loc = (index < counter ? start : prev),
045.                         *ptr = NULL;
046. 
047.             for (uint c = 0; (loc != NULL) && (c < index) && (index < counter); ptr = loc, loc = (*loc).start, c++);
048.             if (loc == NULL) return false;
049. 
050.             if (index == 0)
051.             {
052.                 start = (*loc).start;
053.                 if (start != NULL) (*start).prev = NULL;
054.             } else if (index >= (counter - 1))
055.             {
056.                 prev = (*loc).prev;
057.                 if (prev != NULL) (*prev).start = NULL;
058.             }
059.             else
060.             {
061.                 (*ptr).start = (*loc).start;
062.                 (*loc).start.prev = ptr;
063.             }
064.             arg = (*loc).info;
065.             delete loc;
066.             counter--;
067. 
068.             return true;
069.         }
070. //+----------------+
071.         bool Exclude(const uint index)
072.         {
073.             T tmp;
074. 
075.             return Restore(tmp, index);
076.         }
077. //+----------------+
078.         void Debug(void)
079.         {
080.             Print("===== DEBUG =====");
081.             for (stList <T> *loc = start; loc != NULL; loc = (*loc).start)
082.                 PrintFormat("0x%06X ->> 0x%06X <<- 0x%06X = [%d]", (*loc).start, loc, (*loc).prev, (*loc).info);
083.             Print("=================");
084.         }
085. //+----------------+
086. };
087. //+------------------------------------------------------------------+
088. void OnStart(void)
089. {
090.     stList <char> list;
091. 
092.     list.Store(10);
093.     list.Store(84);
094.     list.Store(-6);
095.     list.Store(47, 0);
096. 
097.     list.Debug();
098. 
099.     list.Exclude(3);
100.     list.Store(35, 2);
101. 
102.     list.Debug();
103. 
104.     for (char info; list.Restore(info, 0);)
105.         Print(info);
106. };
107. //+------------------------------------------------------------------+

Code 07

Code 07 is almost the final version of the doubly linked list implementation. But what we are really interested in is the result it can produce. When you run the code, you will get the result shown below:

Figure 05

Please note that code 07 is much simpler than the others we have seen so far. However, it will be easier for you if you understand the steps needed to achieve this goal. If it had been presented from the very beginning as the first and only code, you would undoubtedly have had a very hard time understanding how it works. But I do not think there is any need for further explanation, given that the changes were made gradually.

Concluding Thoughts

In today's article, we looked at how to implement a fully functional linked list. There is one point left to explain: each read operation removes the element that was read from the list. There are ways to avoid this. Since we have not yet discussed how to work with classes properly, I will not go into detail on this topic just yet. So we will save that question for another time. In the next article, we will discuss where the evolution of the linked list leads. This evolution will result in a new type of data structure.

MQ5	Description
Code 01	Simple list
Code 02	Simple list
Code 03	Simple list