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

Introduction to linked list

LINKED LIST IN C :-

           List means a sequence of items arranged one after another.

• 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.

• Successive elements are connected by pointers.
• Last element points to NULL.
• It can grow ( during insertion) or shrink in size (in deletion) during execution of a program.
• It can be made just as long as required.
• It does not waste memory space. Dynamic memory allocation is often used in linked list.
• Linked lists were developed in 1955–1956 by Allen Newell, Cliff Shaw and Herbert A. Simon at RAND Corporation as the primary data structure for their Information Processing Language. IPL was used by the authors to develop several early artificial intelligence programs, including the Logic Theory Machine, the General Problem Solver, and a computer chess program.

• LISP, standing for list processor, was created by John McCarthy in 1958 while he was at MIT and in 1960 he published its design in a paper in the Communications of the ACM, entitled "Recursive Functions of Symbolic Expressions and Their Computation by Machine, Part I". One of LISP's major data structures is the linked list.

Some Basic Terminology:-

1. malloc() :- malloc() is a system function which allocates a block of memory in the "heap" and returns a pointer to the new block. The prototype for malloc() and other heap functions are in stdlib.h.

2. free() :- free() is the opposite of malloc.

Creating linked list :-

Node :- The type for the nodes which will make up the body of the list.

These are allocated in the heap. Each node contains a single client data

element and a pointer to the next node in the list. 

           struct node {

                                     int data;

                                     struct node* next;

                               } *head, *temp;

A simple baby example of linked list :-

struct node* BuildOneTwoThree() 

{

struct node* head = NULL;

struct node* second = NULL;

struct node* third = NULL;

head = malloc(sizeof(struct node));   // allocate 3 nodes in the heap

second = malloc(sizeof(struct node));

third = malloc(sizeof(struct node));

head->data = 1;                                   // setup first node

head->next = second;                         // note: pointer assignment rule

second->data = 2;                               // setup second node

second->next = third;

third->data = 3;                                  // setup third link

third->next = NULL;

}

INSERTION IN BEGINNING OF A LINKED LIST

Now we will insert data in beginning of the linked list in a temporary variable 'temp' and after insertion we will assign the value of temp in 'head' variable.

Logic:- As we go on inserting data in temp , new temp node data should be assigned into head.

Function:-

        

struct node

{

    int data;

    struct node* next;

}*head,*temp;               // global variable, can be accessed anywhere

void insert(int x)

{

    temp=malloc(sizeof(struct node));

    temp->data=x;

    temp->next=head;   //give the link part to previous head node

    head=temp;             //now assign newly created node as head

}

Read More