Linked List

Programming C tutorial: List

Prerequisite: Call by Value, Call by reference, pointers

In this chapter, you will learn more complex programming skills. I assume you understand the basic concept of programming C.

The basic reason for the list is storing specific information for instance: name, first name, number.

How do we start? First, try to draw a picture and solve the problem with a pencil.

 

Smiley face

 

 

Head is showing to our first Element. Null represents that our next list is empty.pNext is a pointer showing our next element.

The first step is to create a header List.h:

 

#ifndef LIST_H_

#define LIST_H_

struct Listitem{

int value;

struct Listitem* pNext;

};

struct list{

struct Listitem* pF; // First Element};

#endif /* LIST_H_ */

We divide our list in 2 structures.A list represents our head and pointer to the Listitem structure.A listitem represents value and our *pNext next element

 

 

 Second, we need to create List.c File and add following code:

Initialization of the HEAD

struct list init(){
// HEAD initialization
struct list list;

list.pF = NULL;

return list;
}

 Adding items

/*/* * List.h * *  Created on: 25.05.2019 *      Author: Gennadiy Shevtsov */

void addItem(struct list* list,int value){

struct Listitem* hpointer;

hpointer = (struct Listitem*)calloc(1,sizeof(struct Listitem)); // allocate memory

hpointer->value = value;

if(list->pF == NULL){  // is List empty???

list->pF = hpointer; // our HEAD is hpointer

list->pF->pNext = NULL; // next element is empty

}else

{

hpointer->pNext = list->pF; //FILO principle


list->pF = hpointer;

}}

In this code we added our hpointer of type Listitem to allocate memory for our list and put the overloaded value to hpointer.

 

 

How do we delete Elements at the End from Lists?

Let’s draw a picture again:

 

Smiley face

We have to go till the end of the list and delete our last element and add to our predecessor pNext to null.

 

void deleteAtEnd(struct list* list){

 

struct Listitem* hpointer = (struct Listitem*) calloc(1,sizeof(struct Listitem));   

hpointer->value = 0;   

printf(“\n”);   

printf(“deletAtEnd():”);

if(list->pF->pNext == NULL){ // only head?
free(list->pF);// free memory

list->pF = NULL;// set head to empty

}

else {

hpointer->pNext = list->pF; // copy list to hpointer

while(hpointer->pNext->pNext != NULL){
hpointer = hpointer->pNext; // iterate over lists
}
free(hpointer->pNext);

hpointer->pNext = NULL;

}

Try to understand how delete works and you will be able to programm it alone.

 

our Main and output of the List.h and List.c

void output(struct list list){
struct list *l = &list;
printf(“\n”);
if(l->pF == NULL){

printf(“the list is empty”);}

else{

while(l->pF != NULL){

printf(“%d “,l->pF->value);

l->pF = l->pF->pNext;
}
}

}

int main(void) {
struct list l = init();
struct list *hpointer  = &l;
addItem(hpointer,2);
addItem(hpointer,3);

addItem(hpointer,4);

addItem(hpointer,6);

output(l);

deleteAtEnd(hpointer);

output(l);

deleteAtEnd(hpointer);

output(l);

deleteAtEnd(hpointer);

output(l);

deleteAtEnd(hpointer);

output(l);
return EXIT_SUCCESS;

}

Output:

Smiley face

Leave a Reply