Data Structure Tutorial

Programming Approach

Flow Chart

Define Data Structure

DS Problem Solving

Algorithm

DS Data Types

DS Arrays

DS Stack

DS Queue

Number System

Spare matrix

Structure

Polynomials

Application of Stack

DS Linked List

DS Functions

DS Tree

DS Graph

Searching

Exercise Searching

Sorting

Hash Table

DS Questions

Data Structure Linked List

Linked list is a special data structure that provides a more flexible storage system and the various nodes. A linked list is an unordered set of data, not required to be contiguous in memory, yet grouped via links starting from head pointer.Each node is divided into two or more parts, namely the information field and the link field.

Advantages of Linked List:
1. Linked list are dynamic data structure: They can grow or shrink during the execution of a program.
2. Memory Utilization: Memory is allocated when required and de-allocated (removed) when it is no longer required.
3. Insertion and Deletion are easier and efficient: linked list provide flexibility in inserting a data item at a specified position and deletion of a data item form a given position.

Disadvantages of Linked List:
1. More Memory: if the numbers of fields are more, then more memory space is needed. Access to an arbitrary data item is little bit cumbersome and also time consuming.

Types of Linked List:
1. Singly Linked List: A singly linked list is a list which contains a pointer to a next node. A variable FIRST contains either an addressor a pointer to the first node on the list. The last node has no successor node.

Disadvantage of Single Linked List is it can traverse only inone direction.
In C-Language linked list is created using structure, pointers and dynamic memory allocation function (malloc)
2. Doubly Linked List: In a doubly linked list each node is divided in threeparts:First part contains the information of the element, Second part contains the address of the previous node in thelist and third part contains the address of the next node in thelist.Doubly Linked list removes the disadvantage of Linear Linked list as wecan traverse in both the directions.

Advantages of a doubly linked list are:
a) Insertion and deletion are simple as compared to other linked list.
b) Efficient utilization of memory
c) Bi-directional (both forward and backward) traversal helps in efficient and easy accessibility of nodes.
Disadvantages of doubly linked list are:
a) Uses to pointers which result in more memory space requirement.

3. Circular Linked List: They are linear linked lists in which the last node of the list contains the address of the first node of the linkedlist. In a circular list, every node can be accessed from other nodes. Types of Circular linked list are:

a. Circular Single linked list
b. Circular Double linked list

The basic operations to be performed on the linked list are as follows:
1. Insertion
2. Deletion
3. Traversing
4. Searching
5. Concatenation
6. Reverse
Insertion in the beginning:
To insert an element at the beginning of the list just store address of start to link part of new node and store new in start. Following steps required to insert an element in the beginning of the list:
1. Allocate memory for new node
2. Assign start node in the next to a new node
3. Set start to new node
4. Return

Algorithm for inserting a node at the beginning:
Step 1: if ptr = NULL then
print overflow
exit
else
ptr = (node *) malloc (sizeof(node));
endif
Step 2: if start = NULL then
set ptrnum = item
set ptrnext = NULL
set start = ptr
set last = ptr
endif
Step 3: set ptrnum = item
Step 4: set ptr next = start
Step 5: set start = ptr

Insertion at the end:
To insert an element at the end of the list just store the address of new node to link part of last node. Following steps required to insert node at end of the list:
1. Allocate memory for new node
2. If list is empty then start = new and return start
3. Temp = start
4. Do until temp not points to last node
5. Data[new] = x
6. Link[temp] = new
7. Return

Algorithm for inserting a node at the end:
Step 1: if ptr = NULL then
print overflow
exit
else
ptr = (node *) malloc (sizeof(node))
endif
Step 2: set ptrnum = item
Step 3: set lastnext = ptr
Step 4: set last = ptr
Step 5: set last  next = NULL

Algorithm for inserting a node at the specified position:
Step 1: if ptr = "overflow"
Exit
else
ptr = (node *) malloc (sizeof(node))
endif
Step 2: set ptrinfo = item
Step 3: if start = NULL then
set start = p
set p  next = NULL
endif
Step 4: initialize the counters (I) and pointer (node * temp)
set i=0
set temp = start
Step 5: repeat step 6 and 7 until i < loc
Step 6: set temp = temp  next
Step 7: set i = i + 1
Step 8: set p next = temp  next
Step 9: set temp next = p

Deletion form beginning:
An element deleted from the beginning by storing the address of next node to start. Following steps required to delete the node from start.
1. X = data[start]
2. Temp=start
3. Start = link[start]
4. Free temp
5. Return x

Algorithm for deleting the first node:
Step 1: if start = NULL then
printf("Linked list is empty")
exit
endif
Step 2: set ptr = start
Step 3: set start = start next
Step 4: printf("Element deleted is ", ptrinfo)
Step 5: free (ptr)

Deleting the last node:
To delete an element from the end of the list, we first traverse to the secondlast element of the list. Then the last element can be deleted by following these steps.
1. if list is empty then return failure 2. x= data[start]
3. temp = start
4. do until temp points to second last node
5. temp = link[temp]
6. enddo
7. Free [last]
8. Last = temp
9. Return

Algorithm for deleting the last node:
Step 1: if start = NULL then
printf("Linked list is empty")
exit
endif
Step 2: If startnext=NULL then
setptr = start
set start = NULL
print element deleted is ptrinfo
free (ptr)
endif
Step 3: set ptr = start
Step 4: Repeat steps 5 and 6 will ptrnext = NULL
Step 5: set loc = ptr
Step 6: set ptr = ptr next
Step 7: set loc  next = NULL
Step 8: set last = loc
Step 9: free(ptr)

Algorithm for deleting the node from specified position:
Step 1: if ptr = NULL then
print "Underflow"
exit
endif
Step 2: node* temp, node ptr
set i = 0
set *ptr = start
Step 3: Repeat step 4 to 9 until i ≤ 100
Step 4: set temp = ptr
Step 5: set ptr=ptrnext
Step 6: set i = i + 1
Step 7: print ("Element deleted is ", ptrinfo)
Step 8: set temp next = ptrnext
Step 9: free (ptr)