Title Unit III - Lists, Stacks, and Queues – Data Structure and Algorithm.pdf ✅

www.ckundan.com.np 1 Unit III: Linked Lists, Stacks, and Queues – Data Structure and Algorithms Linked List: A linked list is a sequence of data structures, which are connected together via links. Linked List is a sequence of links which contains items. Each link contains a connection to another link. Linked list is the second most-used data structure after array. Following are the important terms to understand the concept of Linked List:  Link: Each link of a linked list can store a data called an element.  Next: Each link of a linked list contains a link to the next link called Next.  LinkedList: A Linked List contains the connection link to the first link called First. Linked List Representation: Linked list can be visualized as a chain of nodes, where every node points to the next node. As per the above illustration, following are the important points to be considered.  Linked List contains a link element called first.  Each link carries a data field(s) and a link field called next.  Each link is linked with its next link using its next link.  Last link carries a link as null to mark the end of the list. Types of Linked List: 1.Singly Linked List Or One Way Chain: Singly linked list can be defined as the collection of ordered set of elements. The number of elements may vary according to need of the program. A node in the singly linked list consist of two parts: data part and link part. Data part of the node stores actual
www.ckundan.com.np 2 information that is to be represented by the node while the link part of the node stores the address of its immediate successor. One way chain or singly linked list can be traversed only in one direction. In other words, we can say that each node contains only next pointer, therefore we cannot traverse the list in the reverse direction. Consider an example where the marks obtained by the student in three subjects are stored in a linked list as shown in the figure. In the above figure, the arrow represents the links. The data part of every node contains the marks obtained by the student in the different subject. The last node in the list is identified by the null pointer which is present in the address part of the last node. We can have as many elements we require, in the data part of the list. Operations on Singly Linked List: a. Insertion In Singly Linked List At Beginning: Inserting a new element into a singly linked list at beginning is quite simple. We just need to make a few adjustments in the node links. There are the following steps which need to be followed in order to insert a new node in the list at beginning.  Allocate the space for the new node and store data into the data part of the node. This will be done by the following statements. ptr = (struct node *) malloc(sizeof(struct node *)); ptr → data = item  Make the link part of the new node pointing to the existing first node of the list. This will be done by using the following statement. ptr->next = head;  At the last, we need to make the new node as the first node of the list this will be done by using the following statement. head = ptr; Algorithm: Step 1: IF PTR = NULL Write OVERFLOW Go to Step 7 [END OF IF]
www.ckundan.com.np 3 Step 2: SET NEW_NODE = PTR Step 3: SET PTR = PTR → NEXT Step 4: SET NEW_NODE → DATA = VAL Step 5: SET NEW_NODE → NEXT = HEAD Step 6: SET HEAD = NEW_NODE Step 7: EXIT b. Insertion In Singly Linked List At The End: In order to insert a node at the last, there are two scenarios which need to be mentioned. 1. The node is being added to an empty list 2. The node is being added to the end of the linked list  In The First Case: The condition (head == NULL) gets satisfied. Hence, we just need to allocate the space for the node by using malloc statement in C. Data and the link part of the node are set up by using the following statements. ptr->data = item; ptr -> next = NULL; Since, ptr is the only node that will be inserted in the list hence, we need to make this node pointed by the head pointer of the list. This will be done by using the following Statements. Head = ptr  In The Second Case: The condition Head = NULL would fail, since Head is not null. Now, we need to declare a temporary pointer temp in order to traverse through the list. temp is made to point the first node of the list. Temp = head