Download to read offline
Linked List in Data Structure
- 1. BIRLA INSTITUTE OFTECHNOLOGY MESRA, JAIPUR CAMPUS NAME :- NIKHIL AGRAWAL ROLL NO :- MCA/25004/18 TOPIC:-LINKED LIST
- 2. Linked List Itis a linear collection of data elements, called nodes, where the linear order is implemented by means of pointers. Nodes are structures made up of data and a pointer to another node. Usually the pointer is called next.
- 3. NODE Each Nodeof a list is comprising of two items - the data and a reference to the next node. The last node has a reference to null. The entry point into a linked list is called the head of the list. It should be noted that head is not a separate node, but the reference to the first node. If the list is empty then the head is a null reference.
- 4. Creating a Node structnode{ int data; // A simple node of a linked list node *next; }*start; start=NULL; /*start points at the first node initialized to NULL at beginning*/
- 5. node* create( intnum) //say num=1 is passed from main { node*ptr; ptr= new node; //memory allocated dynamically if(ptr==NULL) printf(“OVERFLOW”); // no memory available exit(1); else { ptr->data=num; ptr->next=NULL; return ptr; } }
- 6. Arrays VS LinkedList
- 7. TYPES OF LINKEDLIST There are three basic types of linked lists :- 1. Singly linked list. 2. Doubly linked list. 3. Circular linked list.
- 8. SINGLY LINKED LIST Singly linked lists contain nodes which have a data field as well as link field. Each node has only one link part. Each link part contains the address of the next node in the list. Link part of the last node contains NULL value which signifies the end of the node.
- 9. Basic Operations ona list Creating a List Inserting an element in a list Deleting an element from a list Searching a list Reversing a list
- 10. Inserting the nodein a SLL There are 3 cases here:- Insertion at the beginning Insertion at the end Insertion after a particular node
- 11. Deleting a nodefrom a SLL There are 3 cases here:- Deleting the first node Deleting the last node Deleting the intermediate node
- 12. Searching a SLL Searching involves finding the required element in the list. We can use various techniques of searching like linear search or binary search where binary search is more efficient in case of Arrays But in case of linked list since random access is not available it would become complex to do binary search in it. We can perform simple linear search traversal .
- 13. Reversing a linkedlist We can reverse a linked list by reversing the direction of the links between 2 nodes. We make use of 3 structure pointers say p,q,r. At any instant q will point to the node next to p and r will point to the node next to q. For next iteration p=q and q=r. At the end we will change head to the last node
- 14. DOUBLY LINKED LIST Doubly linked list is a linked data structure that consists of a set of sequentially linked records called nodes. Each node contains three fields : :- one is data part which contain data only. :- Two other field is links part that are point or references to the previous or to the next node in the sequence of nodes. The beginning and ending nodes' previous and next links, respectively, point to some kind of terminator, typically a null node to facilitate traversal of the list.
- 15. Can betraversed in either direction. Some operations, such as deletion and inserting before a node, become easier.
- 16. Structure of DLL structnode { int data; node*next; node*previous; //holds the address of previous node };
- 17. INSERTING NODE INDLL. Inserting at beginning Inserting at the end Inserting after a node
- 18.
- 19. CIRCULAR LINKED LIST Circular Linked List is a variation of Linked list in which the first element points to the last element and the last element points to the first element. Both Singly Linked List and Doubly Linked List can be made into a circular linked list. For singly circular linked list:
- 20. In a circularlinked list there are two methods to know if a node is the first node or not. Either a external pointer, list, points the first node or A header node is placed as the first node of the circular list. The header node can be separated from the others by having a dedicated flag variable to specify if the node is a header node or not.
- 22.