Unit-3 Linked List- Data Structures | BCA 3rd Semester 2023

Unit-3 Linked List- Data Structures | BCA 3rd Semester 2023-Hello everyone welcome to the pencilchampions.com website. This website provide Unit -3 Linked list notes in Data structure. This website helpful all student.

Unit-3

List

• A linked list is a linear data structure, in which the elements are not stored at contiguous memory locations. The elements in a linked list are linked using pointers as shown in the below image:

• In simple words, a linked list consists of nodes where each node contains a data field and a reference(link) to the next node in the list.
  

  ---

  Read external link–https://bcastudyguide.com/unit-3-list-2/

  ---

  Why Linked List?

• Arrays can be used to store linear data of similar types, but arrays have the following limitations.

1. The size of the arrays is fixed: So we must know the upper limit on the number of elements in advance. Also, generally, the allocated memory is equal to the upper limit irrespective of the usage.
2. Inserting a new element in an array of elements is expensive because the room has to be created for the new elements and to create room existing elements have to be shifted.

• For example, in a system, if we maintain a sorted list of IDs in an array id[]

id[] = [1000, 1010, 1050, 2000, 2040].

Read more Internal link-https://pencilchampions.com/unit-2-stack-queue-data-structures-bca-3rd-sem-2023/

• And if we want to insert a new ID 1005, then to maintain the sorted order, we have to move all the elements after 1000 (excluding 1000).
• Deletion is also expensive with arrays until unless some special techniques are used. For example, to delete 1010 in id[], everything after 1010 has to be moved.

Advantages over arrays

1. Dynamic size
2. Ease of insertion/deletion

Drawbacks:

1. Random access is not allowed. We have to access elements sequentially starting from the first node. So we cannot do binary search with linked lists efficiently with its default implementation. Read about it here.
2. Extra memory space for a pointer is required with each element of the list.
3. Not cache friendly. Since array elements are contiguous locations, there is locality of reference which is not there in case of linked lists.

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

Following are the various types of linked list.

1. Simple Linked List
2. Doubly Linked List
3. Circular Linked List

Basic Operations

Following are the basic operations supported by a list.

• Insertion − Adds an element at the beginning of the list.
• Deletion − Deletes an element at the beginning of the list.
• Display − Displays the complete list.
• Search − Searches an element using the given key.
• Delete − Deletes an element using the given key.

Insertion Operation

• Adding a new node in linked list is a more than one step activity. We shall learn this with diagrams here. First, create a node using the same structure and find the location where it has to be inserted.
• Imagine that we are inserting a node B(NewNode), between A (LeftNode) and C(RightNode). Then point B.next to C −
• It should look like this −
• Now, the next node at the left should point to the new node.
• This will put the new node in the middle of the two. The new list should look like this −
• Similar steps should be taken if the node is being inserted at the beginning of the list. While inserting it at the end, the second last node of the list should point to the new node and the new node will point to NULL.

Deletion Operation

• Deletion is also a more than one step process. We shall learn with pictorial representation. First, locate the target node to be removed, by using searching algorithms.
• The left (previous) node of the target node now should point to the next node of the target node
• This will remove the link that was pointing to the target node. Now, using the following code, we will remove what the target node is pointing at.
• We need to use the deleted node. We can keep that in memory otherwise we can simply deallocate memory and wipe off the target node completely.

  Doubly Linked List

• Doubly Linked List is a variation of Linked list in which navigation is possible in both ways, either forward and backward easily as compared to Single Linked List. Following are the important terms to understand the concept of doubly 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.
• Prev − Each link of a linked list contains a link to the previous link called Prev.
• LinkedList − A Linked List contains the connection link to the first link called First and to the last link called Last.

Doubly Linked List Representation

• As per the above illustration, following are the important points to be considered.
• Doubly Linked List contains a link element called first and last.
• Each link carries a data field(s) and two link fields called next and prev.
• Each link is linked with its next link using its next link.
• Each link is linked with its previous link using its previous link.
• The last link carries a link as null to mark the end of the list.

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.

Singly Linked List as Circular

• In singly linked list, the next pointer of the last node points to the first node.

Doubly Linked List as Circular

• In doubly linked list, the next pointer of the last node points to the first node and the previous pointer of the first node points to the last node making the circular in both directions.
• As per the above illustration, following are the important points to be considered.
• The last link’s next points to the first link of the list in both cases of singly as well as doubly linked list.
• The first link’s previous points to the last of the list in case of doubly linked list.

Header Linked List in C

• A header node is a special node that is found at the beginning of the list. A list that contains this type of node, is called the header-linked list. This type of list is useful when information other than that found in each node is needed.
• For example, suppose there is an application in which the number of items in a list is often calculated. Usually, a list is always traversed to find the length of the list. However, if the current length is maintained in an additional header node that information can be easily obtained.

Types of Header Linked List

1. Grounded Header Linked List

• It is a list whose last node contains the NULL pointer. In the header linked list the start pointer always points to the header node. start -> next = NULL indicates that the grounded header linked list is empty. The operations that are possible on this type of linked list are Insertion, Deletion, and Traversing.
• Circular Header Linked List
• A list in which last node points back to the header node is called circular linked list. The chains do not indicate first or last nodes. In this case, external pointers provide a frame of reference because last node of a circular linked list does not contain the NULL pointer. The possible operations on this type of linked list are Insertion, Deletion and Traversing.