head is of type Node**. This will contain the address of the address of the first node and this will remain constant irrespective of node addition/deletion. When a node (say Node0) is to be added at the beginning of an existing linked list, the address of that node should be pointed by head. The link part of that node (Node0) will now contain the address of the previous first node (Node1). Note that here head remains unchanged, only the value (node address) pointed by head gets changed.
So, for performing any kind of operation( addition of node, deletion of node, etc.) on the list, always the head will be passed to the respective function as a parameter and you dont have to return anything from those functions because head itself never gets changed.
Note: head is not a node of the linked list. It holds the address of the first node.
Example: Basic operations on a singly linked list
#include <stdio.h>
#include <stdlib.h>
/* Basic operations on a singly linked list */
static int count;
struct Node
{
int data;
Node *link;
};
void Append(Node **head, int data)
{
Node *temp= *head;
if (!temp) /* Adding the first node */
{
temp = (Node*)malloc(sizeof(Node));
++count;
temp->data = data;
temp->link = NULL;
*head = temp;
}
else
{
while(temp->link)
{
temp = temp->link;
}
temp->link = (Node*)malloc(sizeof(Node)); /*create the new node and append it at the end */
++count;
temp = temp->link;
temp->link= NULL;
temp->data = data;
}
}
void Delete(Node **head, int d) /* The will delete the first node containing
the data value as d in this function */
{
Node *temp = *head;
Node *prev = *head;
bool found = false;
if ((*head)->data == d) /* The node to be deleted is the first one */
{
*head = (*head)->link;
free (temp);
--count; /* List will now contain one less node */
found = true;
}
else
{
while(temp) /* Traverse till the last node */
{
if (temp->data == d) /* Node to be deleted is found */
{
prev->link = temp->link;
free(temp);
--count; /* List will now contain one less node */
found = true;
}
else
{
prev = temp;
temp = temp->link;
}
}
}
if (false == found)
{
printf("The given data can't be found from the list...\n");
}
}
void Display(Node** head)
{
Node *temp = *head;
printf("Total count = %d\n", count);
while(temp)
{
printf("%d -->", temp->data);
temp=temp->link;
}
printf("NULL\n");
}
int main()
{
int data = 0;
Node *first_node = NULL;
Node **head = &first_node; /* first node will change, but head will remain the same and it will always point to the newly made first node*/
Append(head, 10);
Append(head, 20);
Append(head, 30);
Append(head, 40);
Append(head, 50);
Display(head);
printf("Enter data to be deleted from the list: ");
scanf("%d", &data);
fflush(stdin);
Delete(head, data);
Display(head);
}
Another way of handling Linked list
|
|
Node1 Node2 Node3 Node4
Fig: 1.3
The above linked list contains 4 nodes . If you want to add a new node (say Node0) to the beginning of the list, just assign the address of the first node (here Node1 ) to the link part of Node0 which will now become the first node of the list.
Note: Contrary to the first example, there is no explicit head keeping track of the first node of the list here. As the first node itself may get changed, we always have to return the address of the first node from all the functions doing addition and deletion of nodes.
Single Linked List Questions
1. How to find out whether a linked list is circular.
2. How to find out whether a linked list has any loop.
3. Write a function to concatenate two list.
4. Reverse a single linked list.
5. Combine two ordered list into a single linked list.
6. Place the elements of a list in increasing order.
Example: Basic operations on a sorted linked list
#include <stdio.h>
#include <stdlib.h>
/* Create the sorted linked list */
struct Node
{
int data;
Node *link;
};
Node* AddData(Node* head, int d)
{
Node *temp = head;
if (!temp)
{
temp = new Node;
temp->data = d;
temp->link = NULL;
head = temp;
}
else
{
bool nodeCreated = false;
Node *prev = temp; /*This will keep track of the previous node */
Node *tempNew = NULL; /* This will be used for the new node creation */
while(temp) /* Traverse till the last node */
{
if(temp->data < d)
{
prev = temp;
temp = temp ->link;
}
else
{
tempNew = new Node;
tempNew->data = d;
if ( prev == temp) /* The newly created Node contains the
samllest data and hence it will be the
first in the linked list */
{
tempNew->link = temp;
head = tempNew;
}
else
{
prev->link = tempNew;
tempNew->link = temp;
}
nodeCreated = true;
break;
}/* End of else */
}/*End of while */
/* Now check if the new node is creted in the linked list */
if (false == nodeCreated) /* The new node should be inserted at the
end of the list */
{
tempNew = new Node;
tempNew->data = d;
tempNew->link = NULL;
prev->link = tempNew; /* At this point temp is NULL, so insert
the new node after the prev which points to
to the last node of the list */
}
else
{
/* Node is already created so, don't do anything */
}
}/* end of outer most else */
return head;
}
void Display(Node *head)
{
while(head)
{
printf("%d ->", head->data);
head= head->link;
}
}
/* The below function will delete the first node containing data as d */
Node* Delete(Node* head, int d)
{
Node* temp = head;
Node* prev = head;
while(temp)
{
if (temp->data > d) /* as this is sorted linked list, no need to
traverse till the end */
{
printf("No node found containing the give data: %d\n", d);
break;
}
else if (temp->data == d)
{
if (prev == temp) /* if the first node to be deleted */
{
head = temp->link;
printf("\n%d deleted\n",temp->data);
delete temp;
break;
}
else
{
prev->link = temp->link;
printf("\n%d deleted\n",temp->data);
delete temp;
break;
}
}
else /* go to the next node */
{
prev = temp;
temp = temp->link;
}
}/* end of while loop */
return head;
}
int main()
{
Node *head=NULL;
head = AddData(head, 16);
head = AddData(head, 15);
head = AddData(head, 12);
head = AddData(head, 17);
head = AddData(head, 19);
head = AddData(head, 11);
Display(head);
head = Delete(head, 12);
head = Delete(head, 19);
head = Delete(head, 11);
Display(head);
}
Linked List using C++
#include<stdlib.h>
#include<string.h>
#include<iostream>
using namespace std;
template <class T>
class LinkedList
{
private:
int nodeCount;
struct Node
{
T *data;
Node *link;
Node(T* newData)
{
this->link = NULL;
this->data = newData;
}
~Node()
{
delete this->data;
}
private:
Node():data(0),link(0){}
}* head;
public:
LinkedList():head(0),nodeCount(0){}
~LinkedList()
{
while(head) /* Delete all the node before destroying LinkedList */
{
Delete(1); /* Delete the first node */
}
}
void Append(T* lineData)
{
Node* temp = head;
if (!temp) /* This is the first node to be created */
{
head= new Node(lineData);
}
else
{
while(temp->link)
{
temp = temp->link;
}
temp->link = new Node(lineData);
}
++nodeCount; /* one new node is created. */
}
void Delete(int n) /* n-th node to be deleted */
{
bool deleted = false;
if(!head) /* list is empty */
{
cout<<"List is already empty: Can't remove node\n";
}
else
{
int count = 0;
Node* temp = head;
Node* prev = head;
if (n<1)
cout<<"n can't be less than 1"<<endl;
else{
while(temp) /* node starts from 0, count should be n-1*/
{
if (count<n-1)
{
prev = temp;
temp = temp->link;
}
else if (count == (n-1)) /* The node to be deleted is found */
{
if (prev == temp) /* if the first node to be deleted */
{
head = head->link;
cout<<temp->data<<" deleted"<<endl;
delete temp;
}
else
{
prev->link = temp->link;
cout<<temp->data<<" deleted"<<endl;
delete temp;
}
--nodeCount; /* Now the list contains one less node */
break;
}
++count;
}/*End of while loop */
}
}
}
void Display();
};
template <class T>
void LinkedList<T>::Display()
{
Node* temp = head;
while(temp)
{
cout<<temp->data<<"-->";
temp = temp->link;
}
cout<<"NULL"<<endl;
}
int main(int argc, char* argv[])
{
// LinkedList<char*> *list_ptr = new LinkedList<char*>();
LinkedList<char> list;
for (int i = 1; i< argc; ++i)
{
char* temp = (char*)malloc(sizeof(char) * sizeof(argv[i]));
strcpy(temp, argv[i]);
list.Append(temp);
}
list.Display();
list.Delete(5); /* Delete the second node */
list.Display();
}
The above progra expects command line argument. To execute the program type the following command:
./a.out India Australia UK US Germany Nepal Finland Canada
Q1. Reverse a single linked list.
Node* Reverse(Node* head)
{
Node *prev=head, *cur=head, *temp=NULL;
if (!head) //head is NULL
{
printf("%s", "The list is empty");
return head;
}
if (prev->link == NULL) // the list has only one node
{
return prev;
}
cur = cur->link; //move cur to point to the 2nd node
prev->link = NULL; //first node sould point to NULL as this will be the last node after the reverse
while(cur)
{
temp = cur;
cur = cur->link;
temp->link = prev;
prev = temp;
}
return prev;
}
Q2. Write a function to concatenate two list.
Node* ConcatenateList(Node* h1, Node* h2) //This will concatenate the 2nd into 1st list
{
Node* temp=h1;
//check if the first list is null, in this case simply return the 2nd list
if (!h1)
return h2;
while(temp->link)
temp= temp->link; //temp will be pointing to the last node of the 1st list after the loop
temp->link= h2;
return h1;
}