Linked List Diploma notes

 Data Structure

UNIT: - 5 (Part - 1)

Linked List: -

 Singly linked list, operations on list.

 Circular linked lists,

 Doubly linked lists

Linked list: -

1. The term Linked list refers to a linear collection of data items.

2. The array implementation uses static structure where as lined list implementation uses dynamic allocated structure.

3. We can use linked list for creating trees and graph.

4. Linked list is a linear data structure which holds groups of Nodes.

5. In linked list each Nodes is divided into two fields.

6. The first filed in known as data field which holds the information of the element and the second filed is known as next field which contains the address of the next node in the list.

 

 

 

Advantage of Linked List: -

1. Due to dynamic in nature we can allocate the memory when required.

2. In linked list operations like insertion and deletion can be easily implemented.

3. By using linked list we can also implement stack and queue.

4. Access of any element is easy and reduces the access time.

Disadvantage of Linked List: -

1. Memory is wasted because pointer required extra memory for storage.

2. We cannot accessed any element randomly, access each node sequentially.

3. In linked list reverse traversing is difficult.

 

Application of Linked List: -

1. Memory Management: -

Linked list are very much useful in managing memory by its virtue of dynamic nature. The unused nodes a can be easily be maintained as a linked list to form a free list and also they can be efficient manage.

2. Polynomial manipulation: -

The operations on polynomial such as addition, subtraction, multiplication etc. can be implemented easily using linked list.

3. Arithmetic on large number: -

We face problem when the large number are added or multiplied the length of the number may cross the limits. Since it required knows only at run-time using linked list.

4. Symbol table implementation: -

Symbols tables are used in compiler construction and related areas. They are like dictionaries containing name and their associated values.

5. Image viewer (Real world application): -

Previous and next images are linked hence we can accessed by next and previous buttons.

6. Web browser (Real world application): -

We can access previous and next searched URL in web browser by pressing back and next button since they are linked as linked list.

7. Music player (Real world application): -

Songs in music player are linked to previous and next song. We can play either from starting or end of the list.

 

    Types of Linked List: -

                1. Singly/ Linear Linked List

                2. Circular Linked List

                3. Doubly Linked List

                4. Circular Doubly Linked List

 

    Singly Linked List: -

1.     A singly linked list is a linear collection of data elements called nodes.

2.     In singly linked list there is an arrow which connects a node to the next node in the list.

3.     The address filed of the last node contains a special value NULL.

4.     Linked list also contains a pointer variable called head which points the first node of the list.

5.     As a new-node added to a list memory for a node is dynamically allocated.

6.     If the head is NULL then the list is said to be empty list of NULL List.

 

Operation of Linked List: -

Insertion Operation: -

Insertion logic varies depending on where in the list the element is going to be inserted first, middle or end.

In all situations it is as simple as making the pointer point to different node hence insertion at any place will be possible.

 

            1. INSERT AT BEGINNING (At first position): -

Insertion at beginning involves inserting any element at the front of the list.

Steps are as follow: -

Step 1: - Create a node using malloc() function.

Step 2: - Make the next node field of new node point to the node pointed by head. 

Step 3: - Make the head pointer point to new node.

 

 

        2. INSERT AT Middle (Between first and last node): -

Insertion at middle involves inserting any element at middle of the list.

Step 1: - Create a node using malloc() function.

Step 2: - Point the new node to its successor by making the next field of new node point to the next of predecessor node.

Step 3: - Make the predecessor node point to new node.

      

 

        3. INSET AT END (After last node): -

Insert in end involves inserting any element at the end of the list.

Step 1: - Create a node using malloc() function.

Step 2: - Make the next field of new node point to NULL.

Step 3: - Make the predecessor node point to new node.

 

Deletion operation: -

Deletion logic varies depending on from where the node is getting deleted from beginning, middle or from the end.     

        1. Delete from beginning (First node): -

Step 1: -        Store the node to be deleted in a temporary pointer.

Step 2: -        Make head point to the first nodes successor in the list.

Step 3: -        Delete the node pointed by temporary pointer.

 

 

        2. Delete from middle: -

Step 1: -        Store the node to be deleted in a temporary pointer.

Step 2: -        Make the predecessor node point to the successor of the node being deleted.

Step 3: -        Delete the node pointed by the temporary pointer.

 

        3. Delete last node: -

Step 1: -        Store the node to be deleted in a temporary pointer.

Step 2: -        Move the NULL pointer to the predecessor next field of last node.

Step 3: -        Delete the node pointed by temporary pointer.

 

 

*************** THE END ***************

 Student Portal: - Click here

Part 2 will uploaded soon keep studying....!!