INFORMATION TECHONOLOGY 2ND YEAR 3RD SEM SUBJECT : DSA SUBJECT CODE : PCC-CS301 ROLL NO. : 11200223009 A SINGLE LINEAR LINKED LIST is a data structure that consists of a sequence of nodes, each containing a data element and a reference (or link) to the next node in the sequence. The first node in the list is called the head, and the last node is called the tail. The tail node's link points to NULL, indicating the end of the list.
Operations on Single Linked List :
The following operations are performed on a Single Linked List Insertion Deletion Display Before we implement actual operations, first we need to set up an empty list. First, perform the following steps before implementing actual operations. Step 1 - Include all the header files which are used in the program. Step 2 - Declare all the user defined functions. Step 3 - Define a Node structure with two members data and next Step 4 - Define a Node pointer 'head' and set it to NULL. Step 5 - Implement the main method by displaying operations menu and make suitable function calls in the main method to perform user selected operation.
INSERTION : Inserting a new node into a single linear linked list
involves creating a new node, assigning the data element to the new node, and updating the references to maintain the list's integrity. The insertion process can be performed at the beginning, end, or at a specific position within the list. 1. Create New Node Allocate memory for a new node and assign the data element to the new node. 2. Update References Adjust the references of the existing nodes to include the new node in the sequence.
3. Insert Node The new node is now successfully inserted into the linked list, maintaining the order and connectivity of the nodes.
DELETION : Deleting a node from a single linear linked list involves
removing the node from the sequence and updating the references to maintain the list's integrity. The deletion process can be performed at the beginning, end, or at a specific position within the list.
1. Locate Node Identify the node to be deleted by traversing the list and comparing the data element of each node with the target data element.
2. Update References Adjust the references of the nodes before and after the deleted node to maintain the connectivity of the list.
3. Free Memory Release the memory occupied by the deleted node, making it available for future use.
TRAVERSAL : Traversing a single linear linked list involves visiting each
node in the sequence, starting from the head and following the references to the next node. This process is typically used to access the data stored in each node or to perform operations on the list, such as searching for a specific element or inserting a new node.
1. Start at Head Begin the traversal at the head node, which is the first node in the list.
2. Follow Reference Follow the reference (or pointer) from the current node to the next node in the sequence. 3. Repeat Repeat the process of following the reference until you reach the tail node, which has a NULL reference, indicating the end of the list.
ADVANTAGES : Single linear linked lists offer several advantages over
other data structures, making them suitable for various applications. Their dynamic nature allows for efficient insertion and deletion of nodes, while their sequential structure provides a simple and intuitive way to access data. 1. Dynamic Memory Allocation Linked lists can grow or shrink dynamically as needed, allowing for efficient memory management. 2. Efficient Insertion and Deletion Inserting or deleting nodes in a linked list can be done in constant time, regardless of the list's size.
Disadvantages : While single linear linked lists offer advantages, they
also have some disadvantages that should be considered when choosing a data structure for a particular application. Their sequential nature can make random access to data inefficient, and they require additional memory for storing references.
Applications : Single linear linked lists are widely used in various
applications, including operating systems, databases, and software development. Their dynamic nature and efficient insertion and deletion capabilities make them suitable for tasks such as managing memory, implementing queues, and representing graphs.
Operating Systems : Linked lists are used in operating systems for
managing memory, scheduling processes, and implementing file systems.
Databases : Linked lists are used in databases for storing and retrieving data, particularly in situations where the data is dynamically changing.
