LINKED LIST

LINKED LISTS



In this tutorial you will learn about C Programming - Linked Lists, Structure,

Advantages of Linked List, and Types of linked list and Applications of linked

lists.



Linked lists are a type of data structure for storing information as a list.


They are a memory efficient alternative to arrays because the size of the list

is only ever as large as the data.


Plus they do not have to shift data and recopy when resizing as dynamic arrays

do.



They do have the extra overhead of 1 or 2 pointers per data node, so they make

sense only with larger records.


You would not want to store a list of integers in a linked list because it

would actually double your memory overhead over the same list in an array.



There are three different types of linked lists, but the other two are just

variations of the basic singly linked list.


If you understand this linked list then you will be able to handle other two

types of lists.



ADVANTAGES OF LINKED LISTS



A linked list is a dynamic data structure and therefore the size of the linked

list can grow or shrink in size during execution of the program.


A linked list does not require any extra space therefore it does not waste

extra memory. It provides flexibility in rearranging the items efficiently.


The limitation of linked list is that it consumes extra space when compared to

a array since each node must also contain the address of the next item in the

list to search for a single item in a linked list is cumbersome and time

consuming process.


LINKED LISTS TYPES



There are 4 different kinds of linked lists:

LINEAR SINGLY LINKED LIST
CIRCULAR SINGLY LINKED LIST
TWO WAY OR DOUBLY LINKED LIST
CIRCULAR DOUBLY LINKED LIST.



LINKED LIST NODES



A linked list gets their name from the fact that each list node is "linked" by

a pointer. A linked list node is comparable to an array element.


A node contains a data portion and a pointer portion, and is declared as

structs in C.


As an example, we can implement a list of high scores for a game as a linked

list.


Let us now declare a node:


Sample Code

STRUCT LLNODE {
CHAR NAME[10];
INT POINTS;
STRUCT LLNODE *NEXT;
};

We have two variables that make up the data portion of the node, and then the

pointer to the next node in the list.



CREATING LINKED LISTS



A linked list always has a base node that is most commonly called a head, but

some call it as a root. An empty linked list will have this node and will be

set to NULL.


This goes for all three types of linked lists. The last node in a linked list

always points to NULL.


Let us declare our linked list for implementing high scores list.

STRUCT LLNODE *HEAD = NULL;

Here we just declared a regular pointer variable of the node struct we

declared, and then set the head to NULL to indicate the list is empty.


TRAVERSING A LINKED LIST



Moving through a linked list and visiting all the nodes is called traversing

the linked list. There is more than one way to encounter segmentation faults

when traversing a linked list, but if you are careful and follow 2 basic

checks you will be able to handle segmentation faults.



To traverse a singly linked list you create a pointer and set it to head.

Often called the current node as a reminder that it is keeping track of the

current node.


Always make sure to check that head is not NULL before trying to traverse the

list or you will get a segmentation fault.


You may also need to check that the next pointer of the current node is not

NULL, if not, you will go past the end of the list and create a segmentation

fault.



Here is a failsafe way of traversing a singly linked list:

Sample Code

IF (HEAD != NULL) {
WHILE (CURRENTNODE->NEXT != NULL) {
CURRENTNODE = CURRENTNODE->NEXT;
}
}

We first check that the head is not NULL and if so, as long as the current

pointer's next is not NULL, we set current equal to the next node effectively

moving through the entire list until we do encounter a next pointer that is

NULL.



If you follow that formula, you will have no problems with segmentation faults

during traversal


SINGLY LINKED LIST



EXAMPLE PROGRAM

For demonstration of singly linked lists, we have high scores for a game

example. This is quite contrived as an array would clearly be better for this

but it works well for illustrating linked list implementation.

What features do we need for this high scores list? We need to be able to

create a list of players' names, the associated score; we want the results

sorted from greatest score to least score.

Sample Code

#INCLUDE
#INCLUDE
#INCLUDE
// SAMPLE_GAME.C EXFORSYS TUTORIAL. THIS IS ONE WAY
// TO FIX THE ORDER PROBLEM, AND ALSO, THE PROGRAM ISN'T
// WORKING AS ADVERTISED. THE FUNCTION 'FINDPOSITION()' ISN'T
// WORKING AS INTENDED IN THE VERSION SUPPLIED IN EXFORSYS
// TUTORIALS : IT WAS RETURNING POSITION==1 EACH TIME, SUCH
// THAT ADDEND() COULD NEVER BE CALLED. I ADDED EXPLANATIONS
// AND DIAGNOSTICS SUCH THAT YOU CAN SEE HOW THE PROCESS
// WORKS WHEN IT OPERATES CORRECTLY. THERE ARE MANY WAYS TO
// ACCOMPLISH THIS AND MANY STYLISTIC POINTS THAT COULD HAVE
// BEEN ADDRESSED, BUT I DIDN'T WANT TO GET CARRIED AWAY.
// BESIDES, THOSE EXERCISES LIKELY SHOULD BE LEFT TO THE STUDENT
// WHO MIGHT ALSO LIKE TO TRY OTHER DATASET TEST CASES TO PRODUCE
// A MORE EXHAUSTIVE TEST SCENARIO. [ERNIE CORDELL 10NOVEMBER2011]
//THE NODE FOR A LINKED LIST

STRUCT LLNODE
{
CHAR NAME[10];
INT SCORE;
STRUCT LLNODE *NEXT;
};
//LINKED LIST FOR HIGH SCORES AND NUMBER OF NODES FOR INSERTING IN MIDDLE.
STRUCT LLNODE *HEAD = NULL;
INT LISTLEN = 0;
//FUNCTION THAT ADDS A NEW NODE TO THE BEGINNING OF A LINKED LIST.
VOID ADDFRONT(CHAR NAME[], INT SCORE)
{
PRINTF("CALLING ADDFRONT FOR %S.\N", NAME);
STRUCT LLNODE *TEMPNODE;
//CREATE THE NEW NODE AND COPY DATA.
TEMPNODE = (STRUCT LLNODE *)MALLOC(SIZEOF(STRUCT LLNODE));
STRCPY(TEMPNODE->NAME, NAME);
TEMPNODE->SCORE = SCORE;

//2 CASES: BEGINNING OF EMPTY LIST OR BEGINNING OF UNEMPTY LIST.
IF (HEAD == NULL)
{
HEAD = TEMPNODE;
HEAD->NEXT = NULL;
}
ELSE
{

//INSERT THE NEW NODE BEFORE CURRENT HEAD, THEN MAKE THE NEW NODE

THE HEAD.
TEMPNODE->NEXT = HEAD;
HEAD = TEMPNODE;
}
}

//FUNCTION THAT ADDS A NEW NODE TO THE END OF A LINKED LIST.

VOID ADDEND(CHAR NAME[], INT SCORE)
{
PRINTF("CALLING ADDEND FOR %S.\N", NAME);
STRUCT LLNODE *TEMPNODE = (STRUCT LLNODE *)MALLOC(SIZEOF(STRUCT
LLNODE));
STRUCT LLNODE *CURRENTNODE = TEMPNODE;

//CREATE THE NEW NODE AND COPY DATA.

STRCPY(TEMPNODE->NAME, NAME);
TEMPNODE->SCORE = SCORE;

//TRAVERSE THE LIST TO THE LAST NODE.

IF (HEAD == NULL)
{
HEAD = TEMPNODE;
TEMPNODE->NEXT = NULL;
}
ELSE
{
CURRENTNODE = HEAD;
WHILE (CURRENTNODE->NEXT != NULL)
{
CURRENTNODE = CURRENTNODE->NEXT;
}

//SET THE NEW NODE'S POINTER TO NULL.

TEMPNODE->NEXT = NULL;

//SET THE LAST NODE POINTER'S NEXT TO THE NEW NODE.

CURRENTNODE->NEXT = TEMPNODE;

}
}

//DETERMINES WHICH POSITION IN THE LIST A NODE SHOULD BE PLACED. NOT

RELATED TO

INT FINDPOSITION(INT SCORE)
{
PRINTF("CALLING FINDPOSITION . . . \N");
STRUCT LLNODE *CURRENTNODE;
INT POSITION = 1;

//IF THE LIST IS NOT EMPTY, TRAVERSE IT.

PRINTF("THE ADDRESS OF HEAD IS %P.\N", HEAD);
CURRENTNODE = HEAD;
IF (HEAD != NULL)
{
DO
{

//IF THE NEW SCORE IS GREATER THAN THE SAVED SCORE AT THE

NODE, THEN WE

//WANT TO INSERT HERE.

PRINTF("TEMP SCORE: %D, NODE SCORE: %D.\N",
SCORE, CURRENTNODE->SCORE);
IF (SCORE >= CURRENTNODE->SCORE)
RETURN POSITION;

//OTHERWISE TRAVERSE AND TRACK POSITION.

CURRENTNODE = CURRENTNODE->NEXT;
POSITION++;
}
WHILE (CURRENTNODE/*->NEXT */ != NULL);
}
RETURN POSITION;
}

//ADDS A NEW NODE BY DETERMINING WHERE IN THE LIST IT SHOULD GO.
VOID ADDNODE(CHAR NAME[], INT SCORE)
{
PRINTF("\NTCALLING ADDNODE . . . \N");
INT CURRENTPOS = 1;
INT POSITION = FINDPOSITION(SCORE);
PRINTF("POSITION IS %D, LISTLEN IS %D.\N", POSITION, LISTLEN);
STRUCT LLNODE *TEMPNODE = (STRUCT LLNODE *)MALLOC(SIZEOF(STRUCT
LLNODE));
STRUCT LLNODE *PREVIOUSNODE = TEMPNODE;
STRUCT LLNODE *CURRENTNODE;
CURRENTNODE = HEAD;
IF (POSITION == 1)
{

//ADD TO BEGINNING OF LIST.

ADDFRONT(NAME, SCORE);
LISTLEN++;
}
ELSE IF (POSITION > LISTLEN)
{
//ADD TO END OF LIST.
ADDEND(NAME, SCORE);
LISTLEN++;
}
ELSE
{

//ADD SOMEWHERE IN THE MIDDLE OF THE LIST.

WHILE (CURRENTPOS < POSITION) { //TRAVERSE THE LIST UNTIL WE FIND THE LOCATION FOR THE NEW NODE. CURRENTPOS++; PREVIOUSNODE = CURRENTNODE; CURRENTNODE = CURRENTNODE->NEXT;
}
STRCPY(TEMPNODE->NAME, NAME);
TEMPNODE->SCORE = SCORE;
PREVIOUSNODE->NEXT = TEMPNODE;
PRINTF("ADDING %S AFTER %S AND BEFORE %S.\N", TEMPNODE->NAME,
PREVIOUSNODE->NAME, CURRENTNODE->NAME);
TEMPNODE->NEXT = CURRENTNODE;
LISTLEN++;
}
}

//PRINTS ENTIRE LIST.
VOID PRINTLIST()
{
PRINTF("TCALLING PRINTLIST . . . \N");
STRUCT LLNODE *CURRENTNODE;
CURRENTNODE = HEAD;
WHILE (CURRENTNODE != NULL)
{
PRINTF("%S:", CURRENTNODE->NAME);
PRINTF("%D", CURRENTNODE->SCORE);
PRINTF("\N");
CURRENTNODE = CURRENTNODE->NEXT;
}
}

INT MAIN(VOID)
{
CHAR PLAYER1[] = {"JON B."};
CHAR PLAYER2[] = {"TOM D."};
CHAR PLAYER3[] = {"JESSE M."};
CHAR PLAYER4[] = {"TODD"};
CHAR PLAYER5[] = {"MATT"};
INT SCORES[] = {150, 100, 1000, 400, 275};
ADDNODE(PLAYER1, SCORES[0]);
ADDNODE(PLAYER2, SCORES[1]);
ADDNODE(PLAYER3, SCORES[2]);
ADDNODE(PLAYER4, SCORES[3]);
ADDNODE(PLAYER5, SCORES[4]);
PRINTLIST();
STRUCT LLNODE* CURRENT = NULL;
WHILE (HEAD != NULL) // CLEAR LIST (SEAL MEMORY LEAK?)
{
CURRENT = HEAD;
HEAD = CURRENT->NEXT;
FREE(CURRENT);
}
PRINTLIST();
RETURN(EXIT_SUCCESS);
}

Here is the complete source code of the above example


This example models 5 people having played a game with their scores added to a

list of high scores, then it prints the list.

The scores are not entered in any particular order as would happen in real

life so the findposition function takes care of sorting the new nodes

according to the scores before they are put into the list.

Here is the output after running the program.

In the next tutorial we will be learning more about Circular Linked Lists and

Doubly Linked Lists. Feel free to ask any questions you might have.

C DOUBLY LINKED LISTS



In this tutorial you will learn about C Programming - What is Doubly linked

lists, Adding Nodes Doubly linked lists, Traversing a Doubly linked lists and

working with Doubly linked list Example.


Doubly linked lists are the same as singly linked lists, except they have an

extra pointer per node so they point to the next node and the previous node.


You just make sure that whenever you insert a node you set next to the next

node and previous to the previous node.

They will also commonly keep a tail and head pointer so that traversal may

start at either end of the list.


DOUBLY LINKED LIST NODES



A doubly linked list node would look like this:


Sample Code

STRUCT DLLNODE {

ARBITRARY DATA PORTION

STRUCT DLLNODE *NEXT;
STRUCT DLLNODE *PREVIOUS;
};

It contains a data portion and a pointer to both the next and previous nodes

in the list sequence allowing for two-way traversal.


CREATING A DOUBLY LINKED LIST



When creating a doubly linked list, we want to be able to go both ways as well

as be able to start at either end of the list when traversing it. As mentioned

earlier, we use a both a tail and a head pointer to provide this

functionality.



Checking for head being NULL is sufficient for checking for an empty list.



Sample Code

IF (HEAD == NULL) {
//THIS NODE BECOMES THE FIRST AND LAST NODE IN THE LIST.


NEWNODE->PREVIOUS = NULL;
NEWNODE->NEXT = NULL;
HEAD = NEWNODE;
TAIL = HEAD;
}

Pretty much the same as we have done throughout this tutorial with the

singularly linked lists, with the addition of the previous pointer needing to

be set to NULL and the tail also being equal to the new node.


INSERTING NODES



Same as linear singularly linked lists, we can add at the beginning, middle,

or end of a doubly linked list.


Placing a node at the beginning of a doubly linked list is quite simple but an

empty and nonempty must be handled differently.


When the list is empty all you have to do is create the new node, set its next

and previous pointers to NULL, and point the head and tail pointers to it. We

already saw the code for this in the last section.



Inserting a new node at the beginning of a nonempty doubly linked list is a

little tricky, but not impossible. First you create your new node and set its

previous pointer to NULL, but the next pointer to the current head.


Then set the current head's previous pointer to the new node being inserted

to move the old head one up in the list. Now all you have to do is point head

at the new node and you are done.


In code it should look something like this


Sample Code

NEWNODE->PREVIOUS = NULL;
NEWNODE->NEXT = HEAD;
HEAD->PREVIOUS = NEWNODE;
HEAD = NEWNODE;

Insertion of a new node at the end of the list is quite similar although we

use the tail pointer as a reference instead of the head pointer.


Since the empty list case here is identical to the empty list case above for

insert at beginning we will skip it.


To place a node at the end of the nonempty list you create the new node, set

its next pointer to NULL and its previous pointer to the current tail.


Then set the current tail's next pointer to the new node. Now point tail to

the new node which you have inserted a node at the back of the list. Although

it's not in our example, here is a code snippet



Sample Code

NEWNODE->NEXT = NULL;
NEWNODE->PREVIOUS = TAIL;
TAIL->NEXT = NEWNODE;
TAIL = NEWNODE;

Note the similarity to the sample for insertion at the beginning.


Here's the fun part, this is the greatest feature of the doubly linked list.

It's actually so simple though, you may be disappointed.


Forward traversal is identical to singly linked list traversal. Seriously,

there is no difference. This should look familiar.


Sample Code

IF (HEAD != NULL) {
CURRENTNODE = HEAD;
WHILE (CURRENTNODE->NEXT != NULL) {
CURRENTNODE = CURRENTNODE->NEXT;
}
}

With that in mind, you would think that going the other way would be the same

but with the tail pointer. You would be correct.


Sample Code

IF (TAIL != NULL) {
CURRENTNODE = TAIL;
WHILE (CURRENTNODE->PREVIOUS != NULL) {
CURRENTNODE = CURRENTNODE->PREVIOUS;
}
}

DOUBLY LINKED LISTS EXAMPLE



A common thing to do in game programming is to keep a list of objects

currently on the screen. One reason is for updating the screen to make them

appear to move. Linked lists are perfectly suited to this purpose because of

their dynamic nature.


Let's make a list of the x and y coordinates of all objects currently

displayed on a screen for an arbitrary game.


We don't want to do too much because it will take attention away from the main

topic, so all we are going to do is create a list of five objects and print

the locations of each object forwards and then backwards.


There is no limit to what you could do besides simply printing? the

coordinates but this example should be sufficient for the basics.


The sample has one function for adding nodes to the front of the list. It

takes into account the empty and nonempty list cases we learned about above.


Then it creates five objects that have an x and y coordinate, and adds the

nodes to the list by calling the addnode function and passing it the newly

created node, thus making the last node added at the beginning of the list and

the first node added the end.

After the list is created and all the game objects coordinates are known, we

traverse the list from the beginning to the end and print all the x and y

values for each object.


Then we do the same, but start from the tail and go back to the head.


Sample Code

#INCLUDE
#INCLUDE

STRUCT DLLNODE {
INT X;
INT Y;
STRUCT DLLNODE *NEXT;
STRUCT DLLNODE *PREVIOUS;
};

//HERE'S THE DOUBLY LINKED LIST ROOT POINTERS.
STRUCT DLLNODE *HEAD = NULL;
STRUCT DLLNODE *TAIL = NULL;

VOID ADDNODE(STRUCT DLLNODE *NEWNODE) {

IF (HEAD == NULL) {
//THIS NODE BECOMES THE FIRST AND LAST NODE IN THE LIST.
NEWNODE->PREVIOUS = NULL;
NEWNODE->NEXT = NULL;
HEAD = NEWNODE;
TAIL = HEAD;

} ELSE {
//LIST IS NOT EMPTY, INSERT AT FRONT OF LIST.
NEWNODE->PREVIOUS = NULL;
NEWNODE->NEXT = HEAD;
HEAD->PREVIOUS = NEWNODE;
HEAD = NEWNODE;
}
}

VOID MAIN() {
INT I;
INT X, Y;
STRUCT DLLNODE *CURRENT;

//CREATE 5 OBJECTS IN A DIAGONAL LINE ACROSS THE SCREEN FROM EACHOTHER.
FOR (I = 0; I < 5; I++) {     STRUCT DLLNODE *NEWNODE;     X = Y = I;     NEWNODE = (STRUCT DLLNODE *)MALLOC(SIZEOF(STRUCT DLLNODE));     NEWNODE->X = X;
NEWNODE->Y = Y;

ADDNODE(NEWNODE);
}

//TRAVERSE THE LIST AND PRINT THE CURRENT POSITION OF EACH OBJECT.
CURRENT = HEAD;
I = 1;
WHILE (CURRENT != NULL) {
PRINTF("OBJECT %D: ", I);
PRINTF("N");
PRINTF(" X POSITION: %D", CURRENT->X);
PRINTF("N");
PRINTF(" Y POSITION: %D", CURRENT->Y);
PRINTF("N");
I++;
CURRENT = CURRENT->NEXT;
}

//DO THE SAME BUT START AT THE BACK OF THE LIST.
CURRENT = TAIL;
I = 1;
WHILE (CURRENT != NULL) {
PRINTF("OBJECT %D: ", I);
PRINTF("N");
PRINTF(" X POSITION: %D", CURRENT->X);
PRINTF("N");
PRINTF(" Y POSITION: %D", CURRENT->Y);
PRINTF("N");
I++;
CURRENT = CURRENT->PREVIOUS;
}
}

Here is a screenshot after running the example program. As you can see, it

went through the list starting at the beginning then again from the end,

creating the mirror image as seen here.




C CIRCULAR LINKED LISTS



In this tutorial you will learn about C Programming - What is Circular Linked

List, Adding Nodes to Circular Linked Lists, Traversing a Circularly Linked

List and working with Circularly Linked List Example.



Circular linked lists are usually used for a queue or stack type situation, or

for implementing a round robin algorithm in system level programming.


You could also use one for a multiplayer game where you were keeping track of

player's turns where it just repeats until the game ends.



They are exactly the same as a singly linked list, but instead of setting the

next pointer in the last node of the list to NULL, you set it to point to

head.


Hence the name circular. Instead of a head pointer, they commonly use a tail

pointer instead to keep track of the last node.


A cingularly linked list node looks exactly the same as a linear singly linked

list. Here's the node for the example programming example.


Sample Code

STRUCT CLLNODE {
CHAR NAME[4];
STRUCT CLLNODE *NEXT;
};

It should be familiar from the previously introduced linear linked list, just

a data portion and the next pointer.


ADDING NODES TO CIRCULAR LINKED LISTS



Adding nodes and creating new circularly linked lists is very similar to the

linear ones we learned previously. Let's look at our example to illustrate.


Sample Code

VOID ADDNODE(STRUCT CLLNODE *NEWNODE) {
//LIST IS EMPTY. CREATE NEW LIST.


IF (TAIL == NULL) {

TAIL = NEWNODE;
NEWNODE->NEXT = TAIL;

} ELSE {

NEWNODE->NEXT = TAIL->NEXT;
TAIL->NEXT = NEWNODE;
TAIL = NEWNODE;
}
}

That addNode function is all it takes to handle both the empty and non-empty

singularly linked list cases when adding new nodes.


You add at the back of the list in this linked list case and that's one of the

reasons these are used for modeling queues and FIFO stacks.


Just as in the singularly linked list case you first check if the list pointer

(no matter what you are calling it) is NULL.


Then set the tail equal to the new node being added and make its pointer point

back at itself, thus completing the circle.


When there are nodes in the list, you first set the new node's next pointer to

tail->next because you are adding it just after tail, not at tail.


You may be able to see why we use tail pointers rather than head pointers for

circularly linked lists. The head would be 2 pointers away from where we

perform insertions.


After that, you set tail's next pointer to the new node and set tail equal to

the new node. Viola, we have inserted a new node at the end of the list, and

tail is now pointing at it.



TRAVERSING A CIRCULARLY LINKED LIST



Traversing a circularly linked list is a little different than the regular

type, due to the fact that there is no NULL termination to tell you when to

stop.However, we can just use the tail pointer for this purpose as well.


As we see in this snippet of our example program, it's not any more difficult

to traverse, it's just different



Sample Code

IF (TAIL != NULL) {
CURRENT = TAIL->NEXT;

WHILE (CURRENT != TAIL) {

...

CURRENT = CURRENT->NEXT;
}

CURRENT = TAIL;

...
}

We begin with the familiar check for the list's existence. If we have a list,

we set the current pointer to the node after tail.


From here we can just go through the nodes until we return to tail, so we use

a while loop to do that.


The traversal is the same as before in that you just set the current pointer

to the next one at the end of the wile loop.


Now if you want to do something when you get to the tail you must do it after

the while loop traversal, because our condition stopped the traversal at the

node just before tail and started just after it.


As you can see we had to add an addition print out block after the while loop

to be able to see the last node's information printed out.