• List is a term used to refer to a linear collection of data items. A List can be implemented either by using arrays or linked lists.
• Usually, a large block of memory is occupied by an array which may not be in use and it is difficult to increase the size of an array.
• Another way of storing a list is to have each element in a list contain a field called a link or pointer, which contains the address of the next element in the list.
• The successive elements in the list need not occupy adjacent space in memory. This type of data structure is called a linked list.
Linked List
• It is the most commonly used data structure used to store similar type of data in memory.
• The elements of a linked list are not stored in adjacent memory locations as in arrays.
• It is a linear collection of data elements, called nodes, where the linear order is implemented by means of pointers.
Linked List
• In a linear or single-linked list, a node is connected to the next node by a single link.
• A node in this type of linked list contains two types of fields • data: which holds a list element • next: which stores a link (i.e. pointer) to the next node in the list.
Linked List
• The structure defined for a single linked list is implemented as follows:
• The structure declared for linear linked list holds two members • An integer type variable ‘data’ which holds the elements and • Another type ‘node’, which has next, which stores the address of the next node in the list.
struct Node{ int info; struct Node * next; }
Properties of Linked list
• The nodes in a linked list are not stored contiguously in the memory
• You don’t have to shift any element in the list
• Memory for each node can be allocated dynamically whenever the need arises.
• The size of a linked list can grow or shrink dynamically
Types of Linked List
• Singly Linked List
• Doubly linked list
• Circular linked list
• Circular doubly linked list
Singly Linked List
• A singly linked list is a dynamic data structure which may grow or shrink, and growing and shrinking depends on the operation made.
• In this type of linked list each node contains two fields one is data field which is used to store the data items and another is next field that is used to point the next node in the list.
Doubly Linked List
• A linked list in which all nodes are linked together by multiple number of links i.e. each node contains three fields (two pointer fields and one data field) rather than two fields is called doubly linked list.
• It provides bidirectional traversal.
Circular Linked List
• A circular linked list is a list where the link field of last node points to the very first node of the list.
• Complicated linked data structure.
• A circular list is very similar to the linear list where in the circular list pointer of the last node points not Null but the first node.
Circular Doubly Linked List
• A circular doubly linked list is one which has the successor and predecessor pointer in circular manner.
• It is a doubly linked list where the next link of last node points to the first node and previous link of first node points to last node of the list.
• The main objective of considering circular doubly linked list is to simplify the insertion and deletion operations performed on doubly linked list
Creating a Linked List
• The head pointer is used to create and access unnamed nodes.
• The above statement obtains memory to store a node and assigns its address to head which is a pointer variable.
struct Node{
int info; struct Node* next;
};
typedef struct Node NodeType;
NodeType* head;
head=(NodeType *) malloc (sizeof( NodeType ) );
Creating a Node
• To create a new node, we use the malloc function to dynamically allocate memory for the new node.
• After creating the node, we can store the new item in the node using a pointer to that node.
• Note that p is not a node; instead it is a pointer to a node.
Nodetype *p; p=(NodeType *) malloc (sizeof( NodeType ) ); p->info=50; p->next = NULL;
Creating an empty list
void createEmptyList(NodeType *head) { head=NULL; }
OR SIMPLY
NodeType *head =Null;
Inserting an Element
• While inserting an element or a node in a linked list, we have to do following things:
• Allocate a node
• Assign a data to info field of the node.
• Adjust a pointer
• We can insert an element in following places
• At the beginning of the linked list
• At the end of the linked list
• At the specified position in a linked list
An algorithm to insert a node at the beginning of the singly linked list
Let *head be the pointer to first node in the current list
1. Create a new node using malloc function NewNode=(NodeType*)malloc(sizeof(NodeType));
2. Assign data to the info field of new node NewNode->info=newItem;
3. Set next of new node to head NewNode->next=head;
4. Set the head pointer to the new node head=NewNode;
5. End
Inserting a node at the beginning of the singly linked list
An algorithm to insert a node at the end of the singly linked list
let *head be the pointer to first node in the current list
1. Create a new node using malloc function NewNode=(NodeType*)malloc(sizeof(NodeType));
2. Assign data to the info field of new node NewNode->info=newItem;
3. Set next of new node to NULL NewNode->next=NULL;
4. if (head ==NULL) then Set head =NewNode.and exit.
5. Set temp=head; 6. while(temp->next!=NULL) temp=temp->next; //increment temp 7. Set temp->next=NewNode;
8. End
0 Comments