Share this post on:

Here we will se that how we can Traverse a Linked list, Traversal means visiting each node, starting from the first node till we reach the last node. For this we will take a structure pointer p which will point to the node that is currently being visited. Initially we have to visit the first node so p is assigned the value of start.

p=start;

Now p points to the first node of linked list. we can access the info part of first node by writing p–>info. Now we have to shift the pointer p forward so that it points to the next node. This can be done by assigning the address of the next node to p as-.

p=p=>link;

Now p has address of the next node. Similarly we can visit each node of linked list through this assignment until p has NULL value, which is link part value of last element. So the linked list can be traversed as –

while(p!=NULL)

{

printf(“%d “,p->info);

p=p->link;

}

Let us take an example to understand how the assignment p=p->link makes the pointer p moves forward. from now onwards we will not show the addresses.

Example: Write a program to function display() the content of the linked list?

void display(struct node *p)

{

struct node *p;

if(start == NULL)

{

printf(“List is empty\n”);

return;

}

p=start;

printf(“List is \n”);

while(p != NULL)

{

printf(“%d “,p->info);

p=p->link;

}

printf(“\n\n”);

}

Don’t think of using start for moving forward. If we use start=start->link, instead of p=p->link then we will lose start and that is the only means of accessing our list. The following function count() find out the number of elements of the linked list.

void count(struct node *start)

{

struct node *p;

int cnt=0;

p=start;

while(p!=NULL)

{

p=p->link;

cnt++;

}

printf(“Number of elements are %d\n”,cnt);

}

Searching in a Linked List

For searching an element, we traverse the linked list and while traversing we compare the info part of each element with the given element to be searched. In the function given below, item is the element which we want to search.

Example:

void search(struct node * start,int item)

{

struct node *p=start;

int pos=1;

while(p!=NULL)

{

if(p->info == item)

{

printf(“Item %d found at position %d\n”,item, pos);

return;

}

p=p->link;

pos++;

}

printf(“Item %d not found in list\n”,item);

}

Insertion in a Linked List

There can be four cases while inserting a node in a linked list.

  1. Insertion at the beginning.
  2. Insertion in an empty list.
  3. Insertion at the end.
  4. Insertion in between the list nodes.

To insert a node, initially we will dynamically allocate space for that node using malloc(). Suppose tmp is a pointer that points to this dynamically allocated node. in the info part of the node we will put the data value.

tmp=(struct node *)malloc(sizeof(struct node));

tmp->info=data;

The link part of the node contains garbage value; we will assign address to it separately in the different cases. In our explanation we will refer to this new node as node T.

Share this post on:
Avatar Raiyan

Author: Raiyan

Hi, I guess you're here because you want to know a bit about me. huh? I am not so good on talking about myself but I'll give a short about me.

My Name is Raiyan. I am a Professional Application Developer and a Blogger.
I started this website to Share my Knowledge. Here I provide all my knowledge whatever I earned till now.

Leave a Comment

Your email address will not be published. Required fields are marked *