Traversing a Linked List

The word "traverse" means "to go or travel across or over".

Uses of traversal:-

• If we want to modify each of the elements in the list then we need to travel across each element , there comes the need of traversal. 

e.g. LIST = 1, 2, 3, 4, 5....

        We want to add 0 to each of the element then we shall traverse the linked list.        After traversing the list will be LIST:- 10,20,30,40,50....

Program to traverse a linked  linked list :-

#include <stdio.h>

#include <stdlib.h>

/*www.TheTechmadness.in*/

int list[20];

int link[20];

int start;

void process(int);

void main()

{

    int ptr;

    list[0]=22;list[2]=5;list[3]=19;list[5]=87;list[7]=29;list[8]=79;

    list[9]=33;list[11]=2;list[13]=50;list[14]=8;list[16]=55;list[18]=99;

    link[0]=3;link[2]=13;link[3]=2;link[5]=8;link[7]=14;link[8]=9;link[9]=18;

    link[11]=16;link[13]=5;link[14]=-1;link[16]=0;link[18]=7;

    start=11;

    ptr=start;

    printf("initial list:\n");

    while(ptr!=-1)

    {

        printf("%d\t",list[ptr]);

        ptr=link[ptr];

    }

    ptr=start;

    while(ptr!=-1)

    {

        process(ptr);  //traversing list to apply process

        ptr=link[ptr];

    }

    ptr=start;

    printf("\n\nlist after traversal:\n");

    while(ptr!=-1)

    {

        printf("%d\t",list[ptr]);

        ptr=link[ptr];

    }

    getch();

}

void process(int p1)

{

    list[p1]=list[p1]*10;

}

Output:-

initial list:

2       55      22      19      5       50      87      79      33      99

29      8

list after traversal:

20      550     220     190     50      500     870     790     330     990

290     80

Read More

Linked List

What would you explain linked list to a person?
Consider a linked list to be a train where Engine is the head and you have flexibility to join locomotives or remove them . Each locomotives of the train is analogous to data node in a linked list, locomotives are connected in manner where person can go from locomotives to locomotives as you can traverse a linked list. 

Insertion, deletion: Let's say train company find a locomotive to be faulty. They remove(delete) the faulty locomotive and insert a working locomotive

This would be a doubly linked list, for singly linked list you can put a restriction that person can traverse from head to last locomotives only.

• In computer science, a linked list is a data structure consisting of a group of nodes which together represent a sequence. Under the simplest form, each node is composed of a data and a reference (in other words, a link) to the next node in the sequence; more complex variants add additional links. 

• Unlike arrays , linked list can grow or shrink in size ( size of arrays is fixed e.g. a[10]). There is ease in doing insertion and deletion in linked list than arrays. In arrays , we have to shift elements during any insertion or deletion (if sorting is maintained).

• Unlike arrays, linked list elements are not stored at contiguous location; the elements are linked using pointers.
• That vectors/arrays are almost always faster because hardware memory access is optimized (caching, prefetch) for accessing contiguous addresses.
•  It takes 4- 6 times the memory and 600-1000 times the CPU of a vector.

Uses of Linked List :-

• Linked lists can be used to implement stacks, queues, graphs, etc.
• Linked lists let you insert elements at the beginning and end of the list in O(1) time. This makes for efficient implementations of stacks, queues.
• Linked lists also remove the overhead of bothering about the size of the data structure. The size need not to be known in advance.
• They can also be used for the adjacency list representation of graphs.
• Hash tables with chaining is also possible.

More topics in linked list :-

Introduction and Implementation of linked list

Traversing a linked list

Searching in Linked list

Insertion in Linked list

Deletion in linked list

Reversing Linked list

Header linked list

Circular Linked list

Doubly Linked list

Read More