Link list using array in Data structure amd algorithms

Introduction  A linked list is a linear data structure which is used to store a collection of elements.  Each element in a linked list is represented by node.  It is a best example of dynamic data structure that uses pointer for the implementation  Each node contain two parts  Data part or info part - which is used to store the element  Link part or address part- which is used to stores the link to the next node. Node Data Link

Introduction  Linked list require more memory compare to array for the same size of the elements because along with data or value it also store pointer to next node.  It is the most common and simplest data structure. They can be used to implement other data structure like stack and queue etc.  Finally, we can say that a linked list is a set of dynamically allocated nodes, organized in such a way that each node has a value and a pointer.

Introduction  Arrays and Linked Lists are both linear data stru ctures so they do have some advantages and dra wbacks over each other.  Now let us look at the difference between arrays and linked list.

Arrays Vs Linked List Arrays Linked Lists  Collection of elements of similar data type  Support random access using indexing  Best suitable for fixed size elements implementation  Insertion and deletion of elements are inefficient i.e. elements are usually shifted  An ordered collection of elements of the same type where each element is linked using pointers to th e next one.  Doesn’t support random access  Support Dynamic size  Insertion and deletion of elements are efficient i.e. no shifting

Arrays Vs Linked List Arrays Linked Lists  Memory is allocated statically or compile time  Wastage of memory if the allocated memory is not fully utilized  Data elements are stored in computer memory in contiguous location; so access is faster  Size must be specified at the time of array declaration  Memory is allocated dynamically or run time  There is no wastage of memory  New elements can be stored anywhere, and use pointers to create a reference for the new element; so access is slow  Size of a Linked list grows/shrinks as and when new elements are inserted/deleted.

Types of Linked List  There are two types of linked list  Single or Singly linked list (SLL)  Single Circular Linked List  Double or Doubly linked list (DLL)  Double Circular Linked List

Singly Linked List (SLL)  This is a fundamental type of linked list  Each node has two part  Data or info part- contain actual value or information  Next or link part – contain pointer or address of the next node  Last node contain NULL value in link part which indicated end of the node  Traversing is allowed only in forward direction  It uses less memory as compare to doubly linked list per node ( Single pointer)

Singly Linked List (SLL)  Complexity of insertion and deletion at a known position is O(n)  We prefer SLL If we need to save memory and searching is not required  Singly linked list can mostly be used for stacks

Singly Linked List (SLL)  For Example The above figure shows a singly linked list. The first node is always used as a reference to traverse the list and is called HEAD. The last node points to NULL.

Singly Linked List (SLL)  A Singly linked list can be implemented in C programming langauge using the structure and the pointer. struct node { int data; struct node *next; }; This definition is used to build every node in the list. The data field stores the element , and the next field is a pointer to store the next node's address.

Implementation of SLL in C language #include<conio.h> #include<stdio.h> void main() { struct node { int value; struct node *next; }*a,*b,*c; clrscr(); a->value=5; b->value=6; c->value=7;

Implementation of SLL in C language a->next=b; b->next=c; c->next=NULL; printf("nNode an value=%d and Next =%u",a->value,a- >next); printf("nNode bn value=%d and next =%u",a->next- >value,a->next->next); printf("nNode cn value=%d and next=%u",a->next->next- >value,a->next->next->next); getch(); }

Single Circular Linked List  Each node has two parts like SLL  No beginning and No end  Does not contain NULL pointer like SLL  Last node is connected to first node i.e. link part of last node contain address of first node  Traversing allowed only in forward direction  Time saving when we want to go from last node to first node  A good example where it is used is a timesharing problem solved by operating system

Single Circular Linked List  For example

Doubly Linked List (DLL)  Each node has three parts, one data part and two link part  Data part contain actual value  One link part contain next pointer to point next node  Another link part contain previous pointer to point previous node

Doubly Linked List (DLL) // C language to represent a node for DLL struct node { int info; struct node *next; struct node *prev; };

Doubly Linked List (DLL)  Traversing is possible in both directions i.e. forward and backward directions  Required more memory as compare to SLL for the same size ( two pointers required)  Previous link part value of first node and next link part value of last node has value NULL  Complexity of insertion and deletion at a known position is O(1)  We prefer DLL If we need better performance while searching and memory is not a limitation  Can be used to implement stacks, heaps, binary trees

Doubly Linked List (DLL) For Example:

Doubly Circular Linked List  Each node has three parts like DLL  No beginning and No end  Does not contain NULL pointer like DLL  First node is connected to the last node and Last node is connected to first node i.e. previous pointer of the first node contain address of last node and next pointer of last node contain address of first node  Traversing allowed in both directions i.e. forward and backward directions  Time saving when we want to go from last node to first node and vice versa

Doubly Circular Linked List  For example

Operation performed on Linked List The operations which can be performed on a linked list follow: 1.Creation 2.Insertion 3.Deletion 4.Traversing 5.Searching 6.Concatenation 7.Display

Creation  This operation is used to create a linked list  Memory allocated for nodes Creating first node head = (node*) malloc (sizeof(node)); head -> data = 50; head -> next = NULL;

Insertion  Used to insert a new node in the linked list  Insertion take place at different places such as  At beginning of the linked list  At the end of the linked list  At specified position i.e. between any two nodes  Inserting a node is a more than one step activity  Created node must be in same structure

Insertion  At beginning of the linked list  Here we want to add Node X Before inserting Node X

Insertion After inserting Node X New Node becomes new head of the linked list and next pointer points to the Node A

Insertion  At the end of the linked list  Here we want to add Node X Before inserting Node X

Insertion After inserting Node X next pointer of Node D pointes to new Node X and the value of next pointer of Node D becomes NULL

Insertion  At specified position i.e. between any two nodes  Here we want to add Node X between Node B and Node C Before inserting Node X

Insertion After inserting Node X Here, next pointer of Node B pointes to new Node X and next pointer of Node X pointes to Node C

Inserting a node at the beginning

Inserting After a Given Node  Suppose we are given the value of LOC where either LOC is the location of a node A in a linked list or LOC=NULL, so that ITEM is the first node.

Deletion  Used to delete a node from the list  Deletion take place at different places such as similarly insertion operation  From beginning of the linked list  From the end of the linked list  From specified position i.e. between any two nodes  Deleting a node is a more than one step activity

Deletion  Here we want to delete third node i.e. Node C from the linked list  Next pointer of node B points to Node D  Similarly other deletion process will be done

Deleting the node Following a Given Node Let LIST be a linked list in memory. Suppose we are given the location LOC of a node N in LIST. Furthermore we are given the location LOCP of the node preceding N or. when N is the first node, we are given LOCP=NULL.

Traversing  It is a process of examine all nodes of linked list i.e. one end to the other end  Recursive function is used to traverse a linked list in a reverse order  Going through first node to last node is called forward traversing  Going through last node to first node is called backward traversing

Searching  Process to find a desired element in the linked list  Sequential or linear search is the most common search used in linked list  Traverse all nodes one by one and matches with key value  There are two outcomes  Search is successful, if desired element is found in the linked list  Search is unsuccessful, is desired element is not found in the linked list

Concatenation  Process of appending second list to the end of the first list  After concatenation, the linked list size will increases  This is simply done by pointing next pointer of last node of first linked list to first node of the second linked list

Linked Implementation of Stack

Linked Implementation of Queue LINKQ_INSERT(INFO,FRONT,REAR,AVAIL,ITEM)  1. If AVAIL = NULL then write OVERFLOW and Exit.  2. Set NEW=AVAIL and AVAIL=LINK[AVAIL]  3.Set INFO[NEW]=ITEM and LINK[NEW]=NULL  4.If FRONT =NULL then FRONT=REAR=NEW  Else Set LINK[REAR]=NEW and REAR=NEW  5. EXIT

LINKQ_DELETE(INFO,LINK,FRONT,REAR,A VAIL,ITEM)  1. If FRONT=NULL the write UNDERFLOW and Exit.  2.Set TEMP=FRONT  3.ITEM=INFO[FRONT]  4.FRONT=LINK[FRONT]  5.LINK[TEMP]=AVAIL and AVAIL=TEMP  6. Exit

Link list using array in Data structure amd algorithms

More Related Content

Similar to Link list using array in Data structure amd algorithms

Recently uploaded

Link list using array in Data structure amd algorithms