Programming with C/C++ Language
Linked lists

1. Linked lists : Definitions

Linked lists are a way to store data with structures so that we can automatically create a new place to store data whenever necessary.

We write a struct or class definition that contains variables holding information about something, and then has a pointer to a struct of its type.

Each of these individual struct or classes in the list is commonly known as a node.



On this chain, we store the first node of the list. This is the head of the chain. The pointer is the connector between boxes of the chain.

Every time we add a new box, we use the connectors, that is a pointer. We use the keyword new to create a pointer to a new struct or class.

Each of the boxes is a struct (or class) that has a pointer to another one. Remember that the pointer only stores the memory location of something, it is not that thing, so the arrow goes to the next one.

At the end, there is nothing for the pointer to point to, so it does not point to anything, it should be a null pointer or a dummy node to prevent it from accidentally pointing to a totally arbitrary and random location in memory.

2. Linked lists : Example

Let's construct a sctructure box named node.

This box will contain an integer , and a pointer to the next. Of course, mainy boxes will build a chain of boxes.

struct node {
int x;
node *next;
}; // our structure

int main()
{
node *head;
// We declare the head pointer
// This will be the unchanging first node

head = new node;
// We create an instance of the struct node
// Now head points to a node struct

head->next;
// The node head points to its next pointer

head->next = 0;
// The next pointer is set equal to a null pointer

head->x = 4;
// By using the -> operator, we modify the node where
// a pointer (head in this case) points to.
}

Lets consider a MOBILE who enters the chain from the head, and goes through the chain down the line as long as the connector connects to another box. This connector that links is the pointer.

This is how a program traverses a linked list. The MOBILE will be a pointer to nodes, and it will first point to the first node head, and then, if the head's pointer to the next node is pointing to something, the MOBILE will be set to point to the next node. In this fashion, the list can be traversed.

Now, as long as there is a pointer to something, the traversal will continue. O nce it reaches a null pointer, meaning there are no more nodes (chain boxes) then it will be at the end of the list, and a new node can subsequently be added if so desired.

3. Linked lists : A related program

  
 
struct node {
  int x;
  node *next;
};

int main()
{
  node *head;       // This will not change  
  node *MOBILE;  // MOBILE will point to each node as it traverses the list

  head = new node;  // Set it to actually  point to something
  head->next = 0;  //  as null node 
  head->x = 4;
  MOBILE = head; // The MOBILE points to the first node
  if ( MOBILE != 0 ) {
    while ( MOBILE->next != 0)
	{	
	  cout<< MOBILE->x; // Print the integer of the box where MOBILE is pointing to 
      MOBILE = MOBILE->next; // Continue until next = 0
	  }
	   cout<< MOBILE->x; // This is the last output to notforget 
  } 
  // MOBILE is now at the end of the list
  MOBILE->next = new node;  // Creates a node at the end of the list
  MOBILE = MOBILE->next; // Let's MOBILE points to that node
  MOBILE->next = 0;         // Prevents it from going any further
  MOBILE->x = 3;
}

That is the basic code for traversing a list. The if statement ensures that there is something to begin with , as a first node .

If the if statement is true, then it is okay to try and access the node pointed to by MOBILE. The while loop will continue as long as there is another pointer in the next.

The MOBILE simply moves along. It changes what it points to by getting the address of MOBILE->next.

Finally, the code at the end can be used to add a new node to the end. Once the while loop as finished, the MOBILE will point to the last node in the array.

Note that the MOBILE will move on until there is nothing to move on to. Therefore, MOBILE->next is set to null, so it is okay to allocate a new area of memory for it to point to.

Then the MOBILE traverses one more element (newly added box) and makes sure that it has its pointer to next set to 0 so that the list has an end.

The 0 in MOBILE->next = 0; plays the role of a period at the end of a sentence. It means there is no more beyond.

Finally, the new node has its x value set; equal 3 for example.

To print a linked list, it is necessary to ensure that the last element is printed after the while loop terminates.

The final output within the is statement, and after the while loop is necessary because the while loop will not run once it reaches the last node, but it will still be necessary to output the contents of the next node.

We can remove the initial check for null since if root is null, then MOBILE will be immediately set to null and the loop will never begin; and write:

MOBILE = root;
while ( MOBILE != NULL) {
  cout<< MOBILE->x;
  MOBILE = MOBILE->next;
}

Instead of:

 
MOBILE = root;
if ( MOBILE != 0 ) {
  while ( MOBILE->next != 0 ) {
    cout<< MOBILE->x;
    MOBILE = MOBILE->next;
  }
  cout<< MOBILE->x;
} 

Using CodeBlocs: