News Updates
Advance C and Data Structure Tutorials
· Linked List :-
Advantages and disadvantages of an Array.
· Advantages :-
1) Array locations are easily accessible using array.
2) Array is a useful data structure to store relatively permanent data.
3) Address calculation is very easy since the memory is allocated sequentially.
4) Operations like sorting, merging, traversing and searching become easy with array.
· Disadvantages :-
1) We can not increase the memory location since array is a static data structure.
2) It is relatively time consuming to insert and delete elements in array.
3) Array may lead to wastage of memory space if size declared is more than that of what is required, since size of an array should be declared before execution of program.
List refers to a linear collection of data items.
One way of storing a list in memory is to have two parts, one to store data called info field and second one to store the address of the next node called link (pointer) field. These successive nodes may not occupy adjacent space in memory.
The use of pointer or link to refer element of a data structure implies that elements which are logically adjacent had not be physically adjacent in memory. This type of allocation is called Linked collection.
A Linked List is a linear collection of data items. A list may be defined to consist of an ordered set of elements called nodes, which may vary in number. Anode can be expanded generally in to 2 parts to have info field and a link field as shown below.
The link address of NULL in the last node signals the end of list. NULL is not an address of any possible node but it is a special value which can be mistaken for an address.
It is possible for a list to be no node at all. Such a list is called an empty list, and this is denoted by assigning a value of NULL to FIRST.
· How to Create a Node?
Structure is a user defined data type which stores group of
different data types in one boundary.
To create a node as shown below :-
INFO
LINK
We should define a structure as follow:-
Struct node
{
int info;
struct node * node;
}
struct node * first;
first = (struct node *) malloc (sizeof (node));
· Algorithm to create Link List :-
Node = Node to be linked, having data and address of next node.
First = Pointer pointing to first node.
Last = Pointer pointing to Last node.
Step 1 :- First = NULL
Step 2 :- Allocate memory to node
Step 3 :- Input Information for node
Node -> Data = X
Node -> Next = NULL
Step 4 :- If First = NULL then
First = Address of node
Else
Last -> Next = Address of node
Step 5 :- Last = Address of node
Step 6 :- Repeat Step 2 to Step 5 until user want to terminate.
· Algorithm to Display a List :-
Step 1 :- Temp = First
Step 2 :- Display Temp -> Data
Step 3 :- Temp = Temp -> Next
Step 4 :- Repeat Step 2 to Step 3 until Temp != NULL
· Algorithm to Insert a New node at the beginning of List :-
Step 1 :- Allocate memory to new node.
Step 2 :- Input Information for new node.
Node -> Data = X
Node -> Next = NULL
Step 3 :- Node -> Next = First
Step 4 :- First = Address of new node.
· Algorithm to Insert a new node at Last :-
Step 1 :- Allocate memory to new node.
Step 2 :- Input Information for new node.
Node -> Data = X
Node -> Next = NULL
Step 3 :- Last -> Next = Address of new node
Step 4 :- Last = Address of new node.
· Algorithm to Insert a new node in between first and last node :-
Step 1 :- Allocate memory to new node.
Step 2 :- Input Information for new node.
Node -> Data = X
Node -> Next = NULL
Step 3 :- Accept Position for Insertion
Step 4 :- Initialize Current = First, First = NULL, Count = 1
Step 5 :- Repeat Step 6 until Count < Position and Current != NULL
Step 6 :- Previous = Current
Current = Current -> Next
Count = Count + 1
Step 7 :- If Current = NULL then
Write (‘Not able to Insert’)
Else if Current = position
New -> Next = Current
Previous -> Next = Address of new node
Deleting a Last node in from the list. i.e. change the Last pointer to point the previous node.
Now, we have to store NULL in the Previous -> Next, So that it will
be the last node of list and also Last = =Previous. So that it contains
Address of last node.
Step 1 :- Initialize Current = First and Previous = NULL
Step 2 :- Repeat Step 3 until Current != Last
Step 3 :- Previous = Current
Current = Current -> Next
Step 4 :- Previous -> Next = NULL
Last = Previous
· Algorithm to Delete a node from between first and last node :-
Step 1 :- Initialize Current = First
Previous = NULL and Count = 1
Step 2 :- Accept the position of node to be delete in variable position
Step 3 :- Repeat Step 4 until Count != Position
Step 4 :- Previous = Current
Current = Current -> Next
Count = Count + 1
Step 5 :- Previous -> Next = Current -> Next
· Circularly Linear Linked List :-
Circularly linear linked list is similar to linear list the difference is that, rather than storing NULL in the link field of Last node, we store address of first node in such way from last node we can go directly to first node in the list.
· Algorithm to Create Circular Linked List :-
Node = Node to be linked, having data and address of next node.
First = Pointer pointing to first node.
Last = Pointer pointing to Last node.
Step 1 :- First = NULL
Step 2 :- Allocate memory to node
Step 3 :- Input Information for node
Node -> Data = X
Node -> Next = NULL
Step 4 :- If First = NULL then
First = Address of node
Else
Last -> Next = Address of node
Step 5 :- Last = Address of node
Step 6 :- Last -> Next =First
Step 7 :- Repeat Step 2 to Step 6 until user want to terminate.
· Algorithm to Display Circular Linked List :-
Step 1 :- Temp = First
Step 2 :- Display Temp -> Data
Step 3 :- Temp = Temp -> Next
Step 4 :- Repeat Step 2 to Step 3 until Temp != First
· Algorithm to Insert a New node at the beginning of Circular Linked List :-
Step 1 :- Allocate memory to new node.
Step 2 :- Input Information for new node.
Node -> Data = X
Node -> Next = NULL
Step 3 :- Node -> Next = First
Step 4 :- Last -> Next = First
Step 5 :- First = Address of new node.
· Algorithm to Insert a new node at Last of Circular Linked List :-
Step 1 :- Allocate memory to new node.
Step 2 :- Input Information for new node.
Node -> Data = X
Node -> Next = NULL
Step 3 :- Last -> Next = Address of new node
Step 4 :- Last = Address of new node.
Step 5 :- Last -> Next = First
· Algorithm to Insert a new node in between first and last node in Circular Linked List :-
Step 1 :- Allocate memory to new node.
Step 2 :- Input Information for new node.
Node -> Data = X
Node -> Next = NULL
Step 3 :- Accept Position for Insertion
Step 4 :- Initialize Current = First, First = NULL, Count = 1
Step 5 :- Repeat Step 6 until Count < Position and Current != NULL
Step 6 :- Previous = Current
Current = Current -> Next
Count = Count + 1
Step 7 :- New -> Next = Current
Previous -> Next = Address of new node
· Algorithm to Delete the First node from Circularly Linked List :-
Deleting a Last node in from the list. i.e. change the Last pointer to point the previous node.
Now, we have to store address of First in the Previous -> Next, So that
It will be the last node of list and also Last = Previous. So that it
contains Address of last node.
Step 1 :- Initialize Current = First and Previous = NULL
Step 2 :- Repeat Step 3 until Current != Last
Step 3 :- Previous = Current
Current = Current -> Next
Step 4 :- Previous -> Next = First
Last = Previous
· Algorithm to Delete a node from between first and last node from Circularly Linked List:-
Step 1 :- Initialize Current = First
Previous = NULL and Count = 1
Step 2 :- Accept the position of node to be delete in variable position
Step 3 :- Repeat Step 4 until Count != Position
Step 4 :- Previous = Current
Current = Current -> Next
Count = Count + 1
Step 5 :- Previous -> Next = Current -> Next