Although linked lists sounds kind of scary, don’t worry they are really easy to use once you’ve got a little practice under your belt! Linked lists form the foundation of many data storing schemes in my game!
They are really nice when you don’t know how many of a data type you will need, and don’t want to waste space. They are like having a dynamically allocated string that fluctuates in size as the program runs. Before I really confuse you lets get into a better explanation!
A linked list is a chain of structs or records called nodes. Each node has at least two members, one of which points to the next item or node in the list! These are defined as Single Linked Lists because they only point to the next item, and not the previous. Those that do point to both are called Doubly Linked Lists or Circular Linked Lists. Please note that there is a distinct difference betweeen Double Linked lists and Circular Linked lists. I won’t go into any depth on it because it doesn’t concern this tutorial. According to this definition, we could have our record hold anything we wanted! The only drawback is that each record must be an instance of the same structure. This means that we couldn’t have a record with a char pointing to another structure holding a short, a char array, and a long. Again, they have to be instances of the same structure for this to work. Another cool aspect is that each structure can be located anywhere in memory, each node doesn’t have to be linear in memory!
1: class List
2: {
3: long Data;
4: List* Next;
5: List(long d)
6: {
7: Data = d;
8: Next = NULL;
9: }
10: };
Notice that we define a constructor for our class that sets Next equal to NULL. This is because we need to know when we have reached the end of our linked list. Each Next item that is NOT equal to NULL means that it is pointing to another allocated instance. If it does equal NULL, then we have reached the end of our list.
Starting up
First off, we need to set our Link pointers to some know location in memory. We will create a temp pointer, allocate an instance, then assign our pointers. Something like this:
1: SLList:: SLList()
2: {
3: Head = NULL;
4: Tail=Head;
5: CurrentPtr = Head;
6: }
We have allocated no memory for out link list nodes. So no nodes exist at the time, some call this the smallest possible like list, others require at least one node. I support the first point of view.
Adding a Node
We can actually add nodes in two possible places, the beginning or the end, although the standard seems to be the end. This makes our linked list act kind of like a queue with the head node being the oldest and end pointing to the newest objects. 
This brings up an interesting subject also. How will we use our linked list? This is what makes the linked list so powerful. We could use it as a priority list where the oldest objects get a higher precedence until deleted from the list. We could also use it as a master listing of items that need to be kept track of at one time, deleting object when they need to be, without using any precedence scheme. Here’s some code that will add a node onto the end of the list, and then move the end pointer so that it really does point at the end.
Following is the code to add a node at the start of the link list. If the tail is NULL then we have no nodes and the new node is the tail node.
1: void AddAtStart(int d)
2: {
3: Node * newNode = new Node(d);
4: if (tal == NULL)
5: {
6: tail = newNode;
7: }
8: }
Here we try and add a node at the end of the link list. If there are no nodes in the link list, it is the same as adding a node at the start of the link list so we use that function.
1: void AddAtEnd(int d)
2: {
3: if (tail == NULL)
4: {
5: AddAtStart(d);
6: }
7: else
8: {
9: Node * newNode = new Node(d);
10: tail->next = newNode;
11: tail = newNode;
12: }
13: }
We make another function, add after. This function adds a node after the given node.
1: void AddAfter(Node * p, int d)
2: {
3: Node * newNode = new Node(d);
4: newNode->next = p->next;
5: p->next = newNode;
6: if (p == tail)
7: tail = newNode;
8: }
We will use this function in our sorted addition function. To implement a sorted insertion function, we need to know the node after which the node is to be added. We have four cases:
- The link list is empty
- The given data is less than the head data (to be inserted at the start)
- The given data is greater than the tail node (to be inserted at the end of the node)
- When the data is to be inserted somewhere in the middle
1: void AddSorted(int d)
2: {
3: if (head == NULL)
4: {
5: AddAtStart(d);
6: }
7: else if (d < head->data)
8: {
9: AddAtStart(d);
10: }
11: else if (d > tail->data)
12: {
13: AddAtEnd(d);
14: }
15: else
16: {
17: for (Node * temp = head; temp->next != NULL; temp = temp->next)
18: {
19: if (temp->next->data > d)
20: {
21: AddAfter(temp, d);
22: break;
23: }
24: }
25: }
26: }
Can i get a one small picture from your site?
Sure!