Prepared By : Uday Shah (HOD - IT)
Contact No : 7600044051
E-Mail : rupareleducaion@gmail.com
Link List Introduction
One disadvantage of using arrays to store data is
that arrays are static structures and therefore cannot be easily extended or
reduced to fit the data set.
Arrays are also expensive to maintain new
insertions and deletions.
So we consider
another data structure called Linked Lists that addresses some of the
limitations of arrays.
A linked list is a linear data structure where each element is a separate object.
Each element we will call it a node of a list is comprising of two items - the data and a reference to the next node. The last node has a reference to null. The entry point into a linked list is called the head of the list.
It should be noted that head is not a separate
node, but the reference to the first node. If the list is empty then the head
is a null reference.
A
linked list is a dynamic data structure. The number of nodes in a list is not
fixed and can grow and shrink on demand.
Any
application which has to deal with an unknown number of objects will need to
use a linked list.
Advantages of Linked Lists
·
They
are a dynamic in nature which allocates the memory when required.
·
Insertion
and deletion operations can be easily implemented.
·
Stacks
and queues can be easily executed.
·
Linked
List reduces the access time.
Disadvantages of Linked Lists
·
The
memory is wasted as pointers require extra memory for storage.
·
No
element can be accessed randomly; it has to access each node sequentially.
·
Reverse
Traversing is difficult in linked list.
·
One disadvantage
of a linked list against an array is that it does not allow direct access to
the individual elements. If you want to access a particular item then you have
to start at the head and follow the references until you get to that item.
Applications of Linked Lists
·
Linked
lists are used to implement stacks, queues, graphs, etc.
·
Linked
lists let you insert elements at the beginning and end of the list.
· In Linked Lists we don't need to know the size in advance.
Types of Linked Lists
Singly
Linked List : Singly linked lists contain nodes which have a data part as well
as an address part i.e. next, which points to the next node in sequence of
nodes. The operations we can perform on singly linked lists are insertion,
deletion and traversal.
Doubly Linked List : In a doubly linked list, each node contains two links the first link points to the previous node and the next link points to the next node in the sequence.
Circular
Linked List : In the
circular linked list the last node of the list contains the address of the
first node and forms a circular chain.
Circular Linked List is little more complicated
linked data structure. In the circular linked list we can insert elements
anywhere in the list whereas in the array we cannot insert element anywhere in
the list because it is in the contiguous memory. In the circular linked list
the previous element stores the address of the next element and the last
element stores the address of the starting element. The elements points to each
other in a circular way which forms a circular chain. The circular linked list
has a dynamic size which means the memory can be allocated when it is required.
Application
of Circular Linked List
The real life application where the circular linked list is
used is our Personal Computers, where multiple applications are running. All
the running applications are kept in a circular linked list and the OS gives a
fixed time slot to all for running. The Operating System keeps on iterating
over the linked list until all the applications are completed.
Another example can be Multiplayer games. All the Players
are kept in a Circular Linked List and the pointer keeps on moving forward as a
player's chance ends.
Circular
Linked List can also be used to create Circular Queue. In a Queue we have to
keep two pointers, FRONT and REAR in memory all the time, where as in Circular
Linked List, only one pointer is required.
Traversal
of Linked List :
Traversal a list is the easiest of all the operation on liked list. While Traversing a liked list just keep moving to next node starting with the head and stopping as the null is encountered.
Traversal means movement of Pointer with Top to Bottom and
Bottom to top. Traversal help to
search, display , count and other linked list Operation it also help to find
exact location in Liked List.
Merge
two sorted linked lists
Write a Merge
function that takes two lists, each of which is sorted or Unsorted in
increasing order, and merges the two together into one list which is in
increasing order. Merge should return the new list. The new list should be
made by marge together
For
example the nodes of the
first two lists.
if the first linked list a is
5->10->15 and the other linked list b is 2->3->20, then Merge
should return a pointer to the head node of the merged list
5->2->10->3->15->20.
There
are many cases to deal with: either ‘a’ or ‘b’ may be empty, during processing either ‘a’ or ‘b’ may run out first, and finally there’s the problem of
starting the result list empty, and building it up while going through ‘a’ and
‘b’.
Reversing
of Linked List.
In
the concept of reversing of linked list link should be represent with Null in
the first stapes. Then each and every node inserted at Beginning of the node.
It means there is only one operation and that is insert at beginning.
Data
elements are always inserted at the top of the node and when user select to
traversal from top to bottom then node with display in reverse order.
Following
is some operation that maintain in Linked List.
1.
Insert
2.
Display
3.
Delete
For
example : Insert values in Liked list
is 5 - 4 - 1 – 2 – 3 then output will be
Output
: 3 – 2 – 1 – 4 – 5
Best Of Luck
Please Share and Give your comments.... Thank you
