Friday, June 22, 2012

Linked list structure !!

Linked list is a sequence of lists or nodes in such a way that one node is pointing to the another node and another node pointing to the another node like a train. Node or list contains a data field which stores data or info and another field is for address, which stores the address of the next node and last node address field in the points to the NULL. There are different forms of the linked lists namely
  • Single linked list: is the default linked list
  • double linked list: similar to single linked list, but it contains two address fields
  • circular linked list: Similar to single linked list, but the difference is last node address field pointr to head node and not NULL.
  • trees: Similar to double linke list.

Structure of a linked list: The basic structure of a linked list contains data Field and address field. It is also called singly linked list. Because it stores the address of the another list or node.

Linked list Structure in C:
struct node
{
    int info;
    struct node *next;
};

// creating the head node statically.
struct node head; 
//accessing the data
head.info = 10;
head.next = NULL;

// creating the head node dynamically.
struct node *head; 
//accessing the data
head->info = 10;
head->next = NULL;




Image 1
 

Structure of a linked list in a pictorial view you can see in the right side image 1. It is one node or list  which contains data field as info and address field as ptr.




example of the linked list
Image 2
 Example for the linked list: we can see in the image 2. The linked list with three nodes and last node ptr is NULL. Head node contains the address of the second pointer. And data field of the head node is 10. In the linked list we will be having only head node. using that head node only we need to do the operations.

  

Linked list representation in Memory
Image3
 Actual linked list in Memory: In above picture image2 is pictorial view of the linked list. But actually in memory the node will like in image 3. where address feild ptr stores the address of the another node. Here head node address is 1234 and its ptr field stores the address 3456. Using 3456, we can access the data field and address field of 3456 node. 3456 node may not be next address in the memory. The memory block may be some where in the memory. using the address. like these all the nodes will be linked in the memory. last node of the list address field ptr points to NULL.
 
Doubly linked list:  Structure of the double linked list is given below. Which contains one data feild and two address fields namely previous and next or left and right.

Structure of double linked list:
struct node
{
    int info;
    struct node *left;
    struct node *right;

};

// creating the head node statically.
struct node head; 
//accessing the data
head.info = 10;
head.left = NULL;

// creating the head node dynamically.
struct node *head; 
//accessing the data
head->info = 10;
head->left = NULL;

Structure of double linked list is shown in the image. Which contains one data feild as info and two address fields left and right. left address field contains address of the previous node, right  address field contains the address of the next node. If there is no previous or next node, they will contain NULL address. generally head  node left address pointer contains NULL and last node right address field contains NULL address.


Image1


Image2


Linked list Applications:
  • System programming
  • Memory organization
  • File management implementations.
  • Tree implementations
Here is the complete working linked list C programming language Code.
 

No comments:

Popular Posts