LINKED LIST (CIRCULAR AND DOUBLE)
#1

Presented by
Joydip Ghosh

[attachment=11178]
SEMINAR ON LINKED LIST (CIRCULAR AND DOUBLE)
What is Linked-List

In computer science, a linked list is a data structure that consists of a sequence of data records such that in each record there is a field that contains a reference (i.e., a link) to the next record in the sequence.
Single linked list
This is the most basic type of linked list, with each node containing a single pointer, to the next node.
Multi linked list
More advanced than the single linked list, each node may be connected to many other nodes.
Special case : Doubly linked lists
Circular linked list
With a circular linked list, the last node is connected to the first, to form a circle.
MULTI OR DOUBLY LINKED LIST
In computer science, a doubly-linked list is a linked data structure that consists of a set of data records, each having two special page link fields that contain references to the previous and to the next record in the sequence. It can be viewed as two singly-linked lists formed from the same data items, in two opposite orders.
Basic Structure Of Double Linked List
data: the user's data
next, prev: the address of the next and previous node in the list
Creation Of Single Node
Empty Doubly Linked List
Inserting into a Doubly Linked List
Deleting an element from a double linked list
oldNode=current;
oldNode->prev->next = oldNode->next;
oldNode->next->prev = oldNode->prev;
current = oldNode->prev;
delete oldNode;
Deleting an element from a double linked list
Reply
#2
Presented By:
Priyanka kaushal

[attachment=12016]
LINKED LIST
Data structure and linked list
A linked list
A linked list is data structure that makes it easy to rearrange data without having to move data in memory.
INTRODUCTION
Linked Lists
 A linked list is a series of connected nodes
 Each node contains at least
• A piece of data (any type)
• Pointer to the next node in the list
 Head: pointer to the first node
 The last node points to NULL
A node is a structure that has two parts: the data and one or more
links.
The nodes in a linked list are called self-referential structures. In such a structure, each instance of the structure contains one or more pointers to other instances of the same structural type.
TYPES OF LINKED LISTS
Linked lists are of following types:
LINEAR SINGLY LINKED LIST
CIRCULAR LINKED LIST
DOUBLY LINKED LIST
CONCEPTUAL IDEA
HOW TO BEGIN
Continued…….
BASIC OPERATIONS
 Creating a list •
 Traversing the list •
 Inserting an item in the list •
 Deleting an item from the list •
 Concatenating two lists into one
FOR CREATION:
LIST IS AN ABSTRACT DATA TYPE

What is an abstract data type?
o It is a data type defined by the user.
o Typically more complex than simple data types like, float , int etc.
o focusing on what it does and ignoring how it does its job
Now Why abstract?
o Because details of the implementation are hidden.
o When you do some operations on the list, say insert an element, you just call a function.
o Details of how the list is implemented or how the insert function is written is no longer required.
How to traverse a list
ALGORITHM: let a LIST be a linked list. This algorithm traverse LIST applying an operation PROCESS to each element of LIST. The variable PTR points to the current node
1. Set PTR=START [initialize the pointer].
2.Repeat steps 3 & 4 while PTR!=NULL.
3.Apply PROCESS to INFO[PTR]
4. Set PTR=LINK[PTR] {now PTR points to next node} [endl of loop]
5.Exit
Garbage collection
Suppose a memory space becomes reusable because a node is deleted from a list or an entire list is deleted from a program.
The operating system of a computer may periodically collect all the deleted space onto the free storage list.
Happen in 2 steps:
1. Runs through all lists tagging those cells which are currently in use
2. Then again runs through and then collects free storage list i.e garbage collection.
Overflow and underflow
Before inserting or deleting a linked list we need to check the memory for availability and unavailability.
OVERFLOW: sometimes new data are to be inserted into a data structure but there is no available space i.e free storage list is empty. Insertion happens when AVAIL=NULL
UNDERFLOW:Situation where one wants to delete data from a data structure that is empty. When there is START=NULL there is a deletion.
How to INSERT a node???
Inserting node B
DELETION
DELETING NODE B……

Advantages of linked list
Easily inserted and deleted: Its insertion or deletion does not cause fragmentation
contiguous memory.
Suppose we have enough free memory but it is not continuous block than we cannot use it in case of array but same memory can be used in case of linked l
Linked list are dynamic data structure as they can grow or shrink according to the user requirement.
MEMORY UTILIZATION:
because all the allocation and deallocaton of the memory is done whenever it is required, but in array you have to allocate memory initially.
Some disadvantages
Finally
We can say that…….
 An array is more useful when size is known in advance, needing fast/random access.
 Linked lists are more flexible (faster growth/shrink, insert/delete/move), but have slower access time and use more memory for storage.
Unrolled linked list
store several elements in each list node, increasing cache performance while decreasing memory overhead for references.
ARRAY VS LINKED LIST
Arrays are suitable for
- Randomly accessing any element.
- Searching the list for a particular value
- Inserting or deleting an element at the end.
2.Linked lists are suitable for
-Inserting/Deleting an element.
-Applications where sequential access is required.
-In situations where the number of elements cannot be predicted beforehand.
Linked List Implementation of stack
The implementation of stack uses a Singly linked list.
Linked List is a dynamic data structure. So collection of data can be used which are variable in size and structure.The program executes can grow and shrink to accommodate the data being stored.
The push operation is performed by inserting the element at the front of the list
The pop operation is performed by deleting the element at the front of the list
Drawback of Linked List implementation
All the operations take constant time
Calls to malloc and free are expensive especially in comparison to the pointer manipulation routines.
Application of Doubly Linked List:
In memory management, a doubly linked list is used to maintain both the list of allocated blocks and the list of free blocks by the memory manager of the operating system.
A doubly linked list can be traversed in both directions.
Having 2 pointers in a doubly linked list provides safety, because even if one of the pointers get corrupted the node still remains linked.
Deleting a particular node from a list does not require keeping track of the previous node.
Application of Circular Linked List:
Circular linked list are used to represent arrays that are naturally circular.
for a pool of buffers that are used and released in FIFO order
for a set of processes that should be time-shared in round robin order
Applications that require access to both ends of the list(eg implementation of a queue)
LINKED LIST--REAL WORLD
Linked List play a critical role in applications that help companies and Govt. MANAGE DATA DYNAMICALLY
it is not uncommon to implement the other data structures directly without using a list as the basis of implementation.
implementation
Almost all computer runtime memory environments use a special stack (the "call stack") to hold information about procedure/function calling and nesting in order to switch to the context of the called function and restore to the caller function when the calling finishes. They follow a runtime protocol between caller and callee to save arguments and return value on the stack.
Reply

Important Note..!

If you are not satisfied with above reply ,..Please

ASK HERE

So that we will collect data for you and will made reply to the request....OR try below "QUICK REPLY" box to add a reply to this page
Popular Searches: double box shifing mechanicsm, insertion and deletion in circular linked list is easier as compared to single linked list, seminar report on linked list, database design for hospital management using linked list, circular doubly linked list, bank management using linked listtor speed control dc, circular symentric filter for iris,

[-]
Quick Reply
Message
Type your reply to this message here.

Image Verification
Please enter the text contained within the image into the text box below it. This process is used to prevent automated spam bots.
Image Verification
(case insensitive)

Possibly Related Threads...
Thread Author Replies Views Last Post
  ROBOTIC SURGERY AND TELE-SURGERY: BASIC PRINCIPLES AND DESCRIPTION OF A NOVEL CONCEPT projectsofme 1 2,855 27-02-2012, 01:12 PM
Last Post: seminar paper
  IP Authoring and Integration for HW/SW Co-Design and Reuse seminar class 0 1,401 05-05-2011, 11:07 AM
Last Post: seminar class
  Using the iPhone and iPod Touch for Remote Sensor Control and Data Acquisition project report helper 0 2,028 19-10-2010, 01:05 PM
Last Post: project report helper
  Biometric word list computer science crazy 0 1,129 03-09-2009, 05:27 PM
Last Post: computer science crazy

Forum Jump: