Understanding Linked Lists in Data Structures and Algorithms
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
