Lesson 3: Double Linked List

In to day's lesson, we will be discussing further about double linked list. At first I thought that this was a simple topic to understand, but I soon enough I was proven wrong. Its simple in a way but sometimes it gets really complex.

For today's lesson, the content are going to be the ways to add data to the list, delete data from the list and then print.



But firstly we need to understand what is double linked list is.

Double Linked List

From learning the meaning of linked list, we know that its like a collection of data that are connected by pointers. Double linked list is like single linked list but the data has a pointer that points towards its previous data. Also keep in mind that the first data (head) has its previous pointed towards NULL and the last data (tail) has its next point towards NULL. Why we do this? The reason is so the data will not be pointing towards different set of data and indicates that it is the first or the last data that the collection have.

Adding Data

There are 3 different ways where you can add data; in front, at the end, or in the middle. In this code I will summarize it all up into one long code which I put in a function Push which in linked list means to add. I use conditional push which is asking the user to input the position where the data wants to be pushed.

To add data to the front firstly you need to make the struct to place your input. Then use malloc to be able to reallocate the data just like in single linked list.

code: (Ex. Grocery)

void push(char vegetable[], int qty, int pos){
struct Grocery *curr = (struct Grocery*) malloc(sizeof(struct Grocery));
strcpy(curr->vegetable, vegetable);
curr->qty=qty;

//Push if there is only 1 data
if(head==NULL){
head= tail = curr;
tail->next=NULL;
head->next=NULL;
}else
{
if(pos==1){
//push head
curr->next=head;
head->prev=curr;
head=curr;
head->prev=NULL;
}else if(pos==3){
//push tail
curr->prev=tail;
tail->next=curr;
tail=curr;
tail->next=NULL;
}else{
//push mid
int i=1;
struct Grocery *temp=head;
while(temp!=tail && i!=pos-1){
temp=temp->next;
i++;
}
if(temp->next!=NULL){
temp->next->prev=curr;
curr->next=temp->next;
curr->prev=temp;
temp->next=curr;
}else{
curr->prev=tail;
tail->next=curr;
tail=curr;
tail->next=NULL;
}
}

}
}

Deleting Data

In this part I will describe 2 different methods in deleting data. The first one is letting the user choose which data they want to erase and the second one is erase all of the data. Firstly I will let you see the code to delete certain data. In this code I use the name of the vegetable the costumer will buy. The program will then search for the name of that vegetable and then delete it. Another term for delete in linked list is called pop

Code:(Ex. Buying in a grocery store)

void pop(char vegetable[]){

system("cls");

if(head==NULL){

printf("Sorry no vegetable at store");

getchar();

}else{

if(strcmp(head->vegetable, vegetable)==0){

if(head==tail){

//If there is only 1 data

free(head);

head=tail=NULL;

}else{

//If there is more than 1 data

head=head->next;

free(head->prev);

head->prev=NULL;

}

}else if(strcmp(tail->vegetable, vegetable)==0){

tail=tail->prev;

free(tail->next);

tail->next=NULL;

}else{

struct Grocery *temp=head;

while(temp!=NULL){

if(strcmp(temp->vegetable,vegetable)==0) break;

temp=temp->next;

}

if(temp!=NULL){

temp->next->prev=temp->prev;

temp->prev->next=temp->next;

free(temp);

}

else printf("Sold OUT!");

getchar();

}

}

}

Code: (Delete all data)

void popAll(){

Grocery *temp;

while(head!=NULL){

temp=head;

head=head->next;

free(temp);

}

head=tail=NULL;

}

That is probably all the basics you need to know about double linked list. Next time we will be discussing about Binary Search Tree where its going to be a lot more confusing than Linked list. You will see how confusing it'll be soon enough. Thanks guys for visiting my blog and I'll see you on the next post.