Download as DOCX, PDF, TXT or read online from Scribd
Download as docx, pdf, or txt
You are on page 1/ 4
ASSIGNMENT#2
Name: Muhammad Umer Farooq malik
Reg-No:SP19-BCS-036 Section: 4B QUESTION # 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 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 can not traverse the list in the reverse direction
Advantages of Linked Lists
Dynamic structure (Mem. Allocated at run-time).
We can have more than one datatype.
Re-arrange of linked list is easy (Insertion-Deletion).
It doesn’t waste memory
Its size is not fixed.
It can be extended or reduced according to requirements.
Elements may or may not be stored in consecutive memory available,even then
Disadvantages of Linked Lists
In linked list, if we want to access any node it is difficult.
It is occupying more memory.
If we have to go to a particular element then we have to go through all those elements that come before that element. we cannot traverse it from last & only from the beginning. It is not easy to sort the elements stored in the linear linked list. Applications: The Single Linked list mostly used in Stack and Queue implementations. Same with Hash Map, we use single linked list in hash map structure to prevent data collision. If you want precise answer, like real world applications, you can consider Notepad application or any text editor that you can edit text. Just imagine, how we are doing “delete” and “undo” operations. These operations are linked to each other perfectly thus we are able to do them instantly. Same with music player, how we are playing next song or previous one. Same with Photo viewer. Whenever you think there is possibility that series of events must be aligned in a order, there we will use single linked list. Take example of train, if you want to add a Bogie either you have to take new bogie till end of the train and add or you must spot a place in between bogies and add it.
Diagram:
Coding : public class LinkedListExamples { Node head; // head of list static class Node { int data; Node next; Node(int d) { data = d; next=null; } } /* This function prints contents of the linked list starting from head */ public void display() { Node n = head; while (n != null) { System.out.print(n.data+" \n"); n = n.next; } } /* method to create a simple linked list with 3 nodes*/ public static void main(String[] args) { /* Start with the empty list. */ LinkedListExamples list = new LinkedListExamples();
list.head = new Node(100);
Node second = new Node(200); Node third = new Node(300);
list.head.next = second; // Link first node with the second node
second.next = third; // Link first node with the second node list.display(); } }
