Linked Lists in Data Structures and Algorithms
Dr. T. Kokilavani
Assistant Professor
Department of Computer Science
St. Joseph’s College
Trichy - 620002
Data Structures and Algorithms,
Dr.T.Kokilavani, SJC
1
Linked List
In arrays, block of memory that is required for the
array should be allocated before use.
Once memory is located it cannot be extended any
more. So array is called static data structure.
Linked list is called dynamic data structure, because
amount of memory required can be varied during its
use.
In linked list, adjacency between the elements are
maintained by means of links or pointers.
A link or pointer is the address (memory location) of
the subsequent element.
An element in a linked list is called node.
A node consists of two fields: DATA (to store the
actual information) and LINK (to point to the next
node).
Data Structures and Algorithms,
Dr.T.Kokilavani, SJC
2
Definition
A linked list is an ordered collection of finite,
homogenous data elements called nodes where the
linear order is maintained by means of links or
pointers.
Linked list can be classified into three major groups:
single linked list
circular linked list
double linked list
Data Structures and Algorithms,
Dr.T.Kokilavani, SJC
3
Single Linked List
In a single linked list each node
contains only one link which
points the subsequent node in the
list. This figure shows a linked list
with 6 nodes.
N1, N2, …., N6 are the constituent
nodes in the list.
Header is an empty node (data
content NULL) and only used to
store a pointer to the first node N1.
Starting from the first node one
can reach to the last node whose
link field does not contain any
address rather than a null value.
In a single linked list one can
move from left to right only, that is
why it is called one way list.
Data Structures and Algorithms,
Dr.T.Kokilavani, SJC
4
Representation of a linked list in memory
There are two ways to
represent a linked list in
memory:
1.
Static representation
using array
2.
Dynamic
representation using
free pool of storage
Static representation of a
single linked list maintains
two arrays:
One array for data and
other for links.
Data Structures and Algorithms,
Dr.T.Kokilavani, SJC
5
Dynamic representation
In this method, there is a memory bank (nothing but a
collection of free spaces) and a memory manager ( a program).
During the creation of linked list, whenever a node is required
the request is placed to the memory manager which will then
search the memory bank for the block requested and if found
grants a desired block to the caller.
Another program called garbage collector returns the unused
node to the memory bank, whenever a node is no more in use.
This is called dynamic memory management.
Dynamic representation of linked list uses the dynamic
memory management policy
Data Structures and Algorithms,
Dr.T.Kokilavani, SJC
6
Dynamic representation
A list of available memory space’s pointer is stored in
AVAIL.
If there is a request for node, the AVAIL is searched for
the block of right size.
If AVAIL is null or the block of desired size is not found
memory manager will return a message accordingly.
If the block is found then let it be XY.
Then memory manager will return the pointer of XY to a
temporary buffer, NEW.
The new node XY then can be inserted at any position in
the linked list by changing the pointers of the concerned
nodes.
Data Structures and Algorithms,
Dr.T.Kokilavani, SJC
7
The node XY is inserted at the
end and change of pointers are
shown by the dotted arrows.
This figure shows how a node
is to be returned to the
memory bank.
Data Structures and Algorithms,
Dr.T.Kokilavani, SJC
8
Linked lists are dynamic data structures where memory can be allocated and varied during usage. They consist of nodes with data and links pointing to subsequent elements. Single, circular, and double linked lists are common types. Representation can be static using arrays or dynamic using memory management. Dynamic representation allows flexible memory allocation.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
E N D
Presentation Transcript
Dr. T. Kokilavani Assistant Professor Department of Computer Science St. JoSeph S College Trichy - 620002 Data Structures and Algorithms, Dr.T.Kokilavani, SJC 1
Linked List In arrays, block of memory that is required for the array should be allocated before use. Once memory is located it cannot be extended any more. So array is called static data structure. Linked list is called dynamic data structure, because amount of memory required can be varied during its use. In linked list, adjacency between the elements are maintained by means of links or pointers. A link or pointer is the address (memory location) of the subsequent element. An element in a linked list is called node. A node consists of two fields: DATA (to store the actual information) and LINK (to point to the next node). Data Structures and Algorithms, Dr.T.Kokilavani, SJC 2
Definition A linked list is an ordered collection of finite, homogenous data elements called nodes where the linear order is maintained by means of links or pointers. Linked list can be classified into three major groups: single linked list circular linked list double linked list Data Structures and Algorithms, Dr.T.Kokilavani, SJC 3
Single Linked List In a single linked list each node contains only one link which points the subsequent node in the list. This figure shows a linked list with 6 nodes. N1, N2, ., N6 are the constituent nodes in the list. Header is an empty node (data content NULL) and only used to store a pointer to the first node N1. Starting from the first node one can reach to the last node whose link field does not contain any address rather than a null value. In a single linked list one can move from left to right only, that is why it is called one way list. Data Structures and Algorithms, Dr.T.Kokilavani, SJC 4
Representation of a linked list in memory There are two ways to represent a linked list in memory: 1. Static representation using array 2. Dynamic representation using free pool of storage Static representation of a single linked list maintains two arrays: One array for data and other for links. Data Structures and Algorithms, Dr.T.Kokilavani, SJC 5
Dynamic representation In this method, there is a memory bank (nothing but a collection of free spaces) and a memory manager ( a program). During the creation of linked list, whenever a node is required the request is placed to the memory manager which will then search the memory bank for the block requested and if found grants a desired block to the caller. Another program called garbage collector returns the unused node to the memory bank, whenever a node is no more in use. This is called dynamic memory management. Dynamic representation of linked list uses the dynamic memory management policy Data Structures and Algorithms, Dr.T.Kokilavani, SJC 6
Dynamic representation A list of available memory space s pointer is stored in AVAIL. If there is a request for node, the AVAIL is searched for the block of right size. If AVAIL is null or the block of desired size is not found memory manager will return a message accordingly. If the block is found then let it be XY. Then memory manager will return the pointer of XY to a temporary buffer, NEW. The new node XY then can be inserted at any position in the linked list by changing the pointers of the concerned nodes. Data Structures and Algorithms, Dr.T.Kokilavani, SJC 7
The node XY is inserted at the end and change of pointers are shown by the dotted arrows. This figure shows how a node is to be returned to the memory bank. Data Structures and Algorithms, Dr.T.Kokilavani, SJC 8
