Linked Lists in C

 

Lists

      1  LINK OR POINTER: A pointer also called a link or a reference, is defined to be a variable that give the location of some other variable(point to the next consecutive node), typically of a structure containing data.

 

 

 

If we use pointer to locate all the structures themselves are actually stored, since by using a pointer(hold the address of variable of struct node type, permit the referencing of structure in a uniform way), we can let the computer system itself locate the structure when requires

      2.   LIST:  First one is a dynamic data structure because its size. A list of numbers is type of structure whose size is variable, that is, a list for which numbers can be inserted or deleted, so that, if n=3 then the list contain only 3 numbers and it n=20 then it contain 20 number. Generally the list is based on the concept of information hiding, that is if someone else had already written the functions for handling lists, then we could use them without need to know the details of how lists are kept in memory or how the list operations are actually done.

LINKED LIST: The idea of a linked list is for every structure in the list, to put a pointer into a structure giving the location of the next structure in the list. It consists of a sequence of nodes, each containing arbitrary data fields and one or two references(“links or pointer(Struct list_type *next)”) pointing to the next and/or previous nodes. It is also called a self referential data type.

ADVANTAGES AND DISADVANTAGES OF LINKED LIST

ADVANTAGES

1 .Flexibility: The main advantage of linked list is dynamic storage which provide flexibility.

2.   OverFlow: There is no overflow problem until the computer memory is actually exhausted. Especially when the individual records are quite large, it may be difficult to determine the amount of contiguous static storage. But with dynamic allocation, there is a no need to attempt to make such decision in advance.

3. Changes: Changes, especially insertion and deletion, can be made in a middle of a linked list more quickly. If the structure are large, then it is much quicker to change the value of a few pointers then to copy the structures themselves from one location to another.

       DISADVANTAGES:

1. Space Use: The first drawback of linked list is that the links themselves take spaces-space that might otherwise be needed for additional data. In the most system the pointer requires the same amount of storage(one word) as does an integer. Thus, the lists of integers will require double the space in linked storage that it would require in contiguous storage.

2.  Random Access: The major drawback of linked list is that they are not suited to Random access. Because with a linked list, it may be necessary to traverse a long path to reach the desired node.

3. Access Time: Access to a single node in linked storage may even take slightly more computing time, since it is necessary ,first, to obtain the pointer and then to go the address.

4.  Programming: The writing function to manipulate linked list as a bit more programming sfforts, with practice, this discrepancy wil decrease.

  TYPES OF LINKED LIST

1)      Single or Singly  Linked List

2)      Double or Doubly Linked List

3)      Circular Linked List

4)      Circular Doubly Linked List

SINGLE LINKED  LIST

 

The Linked list(used to maintain a dynamic series of data like “bogies of train” )is a chain of structures in which each structure consists of data as well as pointer, which stores the address of the next logical structure in the list.

 

In a singly linked list, each element contains a pointer to the next element. In singly linked list traversing is possible only in one direction

 

//program of Single Linked List

#include<stdio.h>

#include<conio.h>

struct new_list

                {

                                int value;

                                struct new_list *next_element;

                               

                }n1,n2,n3,n4;          //created 4 nodes of type new_list

               

void main()

                                {

                                                int j;

                                                n1.value=200;

                                                n2.value=400;

                                                n3.value=600;

                                                n4.value=800;

                                               

                                                n1.next_element=&n2;

                                                n2.next_element=&n3;

                                                n3.next_element=&n4;

                                                n4.next_element=0;

                                               

                                                j=n1.next_element->value;

                                                printf("%d\n",j);

                                               

                                                printf("%d\n",n1.next_element->value);

                                                printf("%d\n",n4.next_element->value);

                                                printf("%d\n",n2.next_element->value);

                                                printf("%d\n",n3.next_element->value);

                                }

In this example:

          1.       First a structure named new_list is created. The list contains an integer data variable named value to store data and a pointer variable named next_element to point to next node.

         2.       Then, 4 objects namely n1,n2,n3,n4 are created to access the structure elements .

         3.       In the main() the value for the 4 nodes are assigned.

         4.       Then, the address of n2 is stored in n1, address of n3 is stored in n2, and address of n4 is stored in n3. The address of n4 is assigned zero to indicate the end of the list.

         5.       Finally the value present in 4 nodes are printed.

Single Linked List

DOUBLY LINKED LIST

 

In doubly linked list, the element should have pointers to the right element as well as to its left element. Doubly linked list is defined as a collection of elements, each element consisting of 3 fields:

 

         1.       Pointer to left element

 

         2.       Data field

 

         3.       Pointer to right element

 

//Program Double Linked List

#include<stdio.h>

#include<conio.h>

struct list

                {

                                int value;

                                struct list *next;

                                struct list *previous;

                               

                }n1,n2,n3;

               

void main()

                                {

                                                int j;

                                                clrscr();

                                                n1.value=20;

                                                n2.value=40;

                                                n3.value=60;

                                                n1.next=&n2;

                                                n2.next=&n3;

                                                n2.previous=&n1;

                                                n3.previous=&n2;

                                                n3.next=0;

                                                n1.previous=0;

                                                j=n1.next->value;

                                                printf("%d\n",j);

                                                printf("%d\n",n1.next->value);

                                                printf("%d\n",n1.next->value);

                                                printf("%d\n",n2.next->value);

                                                printf("%d\n",n1.previous->value);

                                                printf("%d\n",n2.previous->value);

                                                printf("%d\n",n3.previous->value);

                                                getch();

                                }

In this Example:

1. First a structure named list is created. The list contains an integer data variable named value to store data, a pointer variable named NEXT to point to next node and a pointer variable PREVIOUS to point to previous node.

2. Then, the 3 objects namely n1,n2,n3 are created to access the structure elements.

3. In the main() the value for nodes n1,n2,n3 are assigned.

4. Then, the address of n2 is stored in n1 and address of n3 is stored in n2. In order to traverse      backwards, the address of n1 is stored in n2 and address of n2 is stored in n3. The address of n3  is assigned a NULL value to depict the end of the list.

5. Finally, the values present in n1,n2,n3 are printed.

Double Linked List

CIRCULAR LINKED LIST

A Circular Linked List, is a linked list in which the node at the tail of the list(only one pointer is used to point to another node or next element), instead of having a NULL pointer, point, back  to the node at the head of the list(the last node’s pointer points to the HEAD node). We then need only one pointer tail to access both ends of the list, Since we know that tail next points back to the head of the list(the last node contains a pointer back to the first node rather than a NULL).

//Program of Circular Linked List

#include<stdio.h>

#include<conio.h>

struct liist

                {

                                int valuee;

                                struct liist *nxt_element;

                               

                               

                }n1,n2,n3;

               

void main()

                                {

                                                int j;

                                                clrscr();

                                                n1.valuee=35;

                                                n2.valuee=65;

                                                n3.valuee=85;

                                                n1.nxt_element=&n2;

                                                n2.nxt_element=&n3;

                                                n3.nxt_element=&n1;

                                                j=n1.nxt_element->valuee;

                                                printf("%d\n",j);

                                                printf("%d\n",n1.nxt_element->valuee);

                                                printf("%d\n",n2.nxt_element->valuee);

                                                printf("%d\n",n3.nxt_element->valuee);

                                                getch();

                                }

In this Example:

       1.       First a structure named “liist” is created. The liist contains an integer data variable named “valuee” to store data and a pointer variable named nxt_element to point to next node.

       2.       Then, the three objects namely n1,n2,n3 are created to access the structure elements.

       3.       In main() the value for nodes n1,2,3 are assigned

       4.       Then the address of n2 is stored in n1 and address of  n3 is stored in 2. Since, it is a circular list, the address of n3 is assigned to n1 instead of NULL value.

       5.       Last, the values are printed(n1,n2,n3)

CircularLinkedList

CIRCULAR DOUBLY_LINKED LIST

In a Circular(last element connected to the end) doubly Linked List(3 parts.. 1st  is information,2nd  is previousField,3rd  is next Field) , the previous pointer of the first node and the next pointer of the last node point to the HEAD node.

//Program of Circular Double Linked List

#include<stdio.h>

#include<conio.h>

struct C_list

                {

                                int vallue;

                                struct C_list *nxt;

                                struct C_list *previouss;

                               

                }no1,no2,no3,h1;

               

void main()

                                {

                                                int jj;

                                                clrscr();

                                                no1.vallue=10;

                                                no2.vallue=15;

                                                no3.vallue=20;

                                                h1.vallue=3;

                                                no1.nxt=&no2;

                                                no2.nxt=&no3;

                                                no3.nxt=&h1;

                                                h1.nxt=&no1;

                                                no1.previouss=&h1;

                                                no2.previouss=&no1;

                                                no3.previouss=&no2;

                                                h1.previouss=&no3;

                                                jj=no1.nxt->vallue;

                                                printf("%d\n",jj);

                                                printf("%d\n",no1.nxt->vallue);

                                                printf("%d\n",no2.nxt->vallue);

                                                printf("%d\n",no3.nxt->vallue);

                                                printf("%d\n",h1.nxt->vallue);

                                                printf("%d\n",no1.previouss->vallue);

                                                printf("%d\n",no2.previouss->vallue);

                                                printf("%d\n",no3.previouss->vallue);

                                                printf("%d\n",h1.previouss->vallue);

                                                getch();

                                }

In this Example:

       1.       First, a structure named  C_list is created. The C_list contains an integer data variable named value to store data, a pointer variable named nxt to point to next node, and a pointer variable named previous to point to previous node.

       2.       Then the 4 objects namely no1,no2,no3,h1 are created to access the structure elements. In this example, these objects act as nodes in a list. The HEAD node(h1) contains the total number of nodes present in the list.

       3.       In main() the values for the nodes are assigned(no1,no2,no3,h1)

       4.       Then, the address of no2 is stored in no1 and the address of no3 is stored in no2. In order to traverse backwards the address of h1 is stored in no3 and address of no1 is stored in h1.

        5.       The values  are printed(no1,no2,no3,h1).

Circular Double Linked List