Memory Allocation/Linked List Method’s Link
Introduction
- A linked list is also known as a ‘Self Referential Structure‘ because a member of the structure/node is declared as a pointer that points to the same (but another) structure/node in the list.
- The structure is the most appropriate data variable to represent the linked list.
- Like arrays, a Linked list is also a primitive data structure.
- A linked list overcomes the disadvantages of an array by providing flexibility in the program.
- Linked list is the second most-used data structure after array.
- A linked list is useful especially when –
- The amount of data to be stored can’t be predicted in advance since it is a dynamic data type.
- Data will frequently be inserted or deleted.
- It is a dynamic data structure.
Definition
- A linked list is a collection of records of the same data type and all the records are connected through pointers.
- A linked list is a non-sequential collection of data items.
- A linked list is a sequence of linked data items, which are connected via links.
Features
- Like arrays, the linked list also has easy/efficient sequential access.
- Linked lists allocate memory for each element separately and only when necessary.
- Unlike an array, in a linked list insertion, deletion, rearrangement of data items, etc. operations are easy and occur at any position in the list because they need a few computations at run time by allocating additional memory space or to release unwanted space. Thus, it optimizes the use of storage space.
- A node of a linked list consists of two parts – The data part and the Address part. The data part stores the user’s data and the address part contains the address of the next connected node and so on. The address part of the last node of a linked list contains NULL.
- For every data item in a linked list, there is an associated pointer that would give the memory location of the next data item in the linked list.
- The data items in the linked list are not in consecutive memory locations. They may be anywhere, but the accessing of these data items is easier as each data item contains the address of the next data item.
- In the linked list, size declaration is optional i.e., it may be more or less than the equal size.
- Memory allocation occurs dynamically i.e., a linked list can grow or shrink its size during the execution of the program as per need.Hence no memory wastage occurs.
- The structure is used in the creation of a linked list which contains different data types that help in making the record.
- A linked list can be made just as long as required.
- It helps to use exactly as much memory as they need by shrinking or expanding it.
- It is used to maintain a dynamic series of data.
- The use of a pointer in a list reduces/eliminates the need for the whole movement of data in memory during basic operations such as insertion, deletion, sorting, etc., and saves time. Thus, a list maintains data items in a logical order rather than a physical order.
Basic Operations in a Linked List
There are the following operations performed in a typical linked list –
- Creation of the List/Linked List.
- Traversing/Printing the list.
- Counting the nodes in the list.
- Inserting new nodes in the list.
- Deleting existing nodes from the list.
- Editing/Modifying/Updating the list.
- Searching individual/specific data items from the list.
- Sorting the list.
- Merging/Concatenating the list.
- Splitting the list.
Advantages/Merits
Linked lists have many advantages. Some of the very important advantages are: –
- Linked lists are dynamic data structures. i.e. they can grow or shrink during the execution of a program as per need.
- Linked lists have efficient memory utilization i.e., Here, memory is not pre-allocated. Memory is allocated whenever it is required and it is de-allocated (removed) when it is no longer needed.
- Insertion and Deletions are easier and more efficient than an array i.e. Linked lists provide flexibility in inserting a data item at a specified position and deletion of the data item from the given position.
- Many complex applications can be easily carried out with linked lists.
Disadvantages/Demerits
- Access to any arbitrary item or data in a linked list is a little cumbersome and time-consuming.
- Searching for a particular element in a list is difficult and also time-consuming.
- It consumes more space than an array with the same number of items because every node requires an additional pointer/ link field to store the address of the next node.
Use/Applications of Linked List
There are the following uses of linked lists in our lives. These are –
- To represent and manipulate polynomial form of structure as
P(x) = a0 Xn + a1 Xn-1 + …… + an-1 X + an - To represent very large numbers in the memory.
- To do operations of heavy numbers such as addition, multiplication, and division.
- To implement stack, queue, trees, and graphs data structures for specific work.
- To implement a symbol table in compiler construction
Types of Linked Lists
There are three main types of linked lists. These are –
(A) Single/Singly/Linear/Simple linked list
(B) Double/Two way linked list
(C) Circular linked list – two types
(a) Single Circular linked list.
(b) Double Circular linked list.
(A) Single linked list
Definition
-
- A single-linked list is one in which all nodes are linked together by a single link in some sequential manner. Hence, it is also called a linear linked list.
Features
-
- A linked list allocates space for each element separately in its own block of memory called a “node”.
- The list gets an overall structure by using pointers to connect all its nodes like the links in a chain.
- Each node contains two fields; a “data” field to store whatever data/element, and a “address” field which is a pointer used to link to the next node.
- Each node is allocated in the heap using malloc() function, so the node memory
continues to exist until it is explicitly de-allocated using free(). - The very first/front/beginning of the list is a pointer that stores the address of the first node of the linked list. It is popularly called the ‘start’ pointer.This “start” pointer which points to the first node. The first node contains a pointer to the second node. The second node contains a pointer to the third node, … and so on. The last node in the list has its next field set to NULL to mark the end of the list.
- Code in a linked list can access any node in the list by starting at the start pointer and following the next pointers. The start pointer is an ordinary local pointer variable, is in the form of stack. The list nodes of a linked list are allocated in the form of a heap.
Syntax/Declaration
struct tag-name
{
Datatype member 1;
Datatype member 2;
.
.
.
Datatype member n;
struct tag-name *pointer;
};
Example
struct student
{
int rollno;
char stuname[30];
float fee;
struct student *ptr;
};
Advantages
-
-
- Simple to Implement.
- Insertions and Deletions is done easily.
- It has dynamic size i.e. not fixed/static i.e. it can be extended or reduced according to requirements.
- Elements are normally stored in scattered form in the memory.
- It is less expensive/cost-efficient.
-
Disadvantages
-
-
- Backward movement is not possible in it.
- Accessing of forward node is very time-consuming.
-
(B) Double Linked List(DLL)
Definition
-
-
- A double-linked list is a type of linked list in which all nodes are linked together by two links/address parts which helps in connecting or accessing both the successor node (next node) and predecessor node (previous node) from any arbitrary node within the list. Thus, each node in a double-linked list has two link fields (pointers) to point or link to the left node (previous) and the right node (next). This helps to traverse in both forward direction and backward direction(Bidirectional).
-
Features
-
-
- A double-linked list is a two-way list in which all nodes have two links/address parts. This helps in connecting or accessing both the successor node and the predecessor node from the given node position.
- It provides bi-directional traversing.
- Each node in a double-linked list contains three fields –
• Left link Part.
• Data Part.
• Right link Part.
Here, the left link connects with the predecessor/previous node, and the right link connects with the successor/next node. The data field stores the required data.
-
Syntax/Declaration
struct tag-name
{
struct tag-name *pointer1;
Datatype member 1;
Datatype member 2;
.
.
.
Datatype member n;
struct tag-name *pointer2;
};
Example
struct student
{
struct student *back;
int rollno;
char stuname[30];
float fee;
struct student *next;
};
Advantages
-
-
- In DLL, we can be traversed in both forward and backward directions from a node, hence searching is easy.
- The insertion and deletion operation in DLL is more efficient than SLL.
-
Disadvantages
-
-
- Every node in DLL requires extra space for an extra back pointer which finally leads to memory overhead.
- All operations require an extra pointer to be maintained.
- They are slightly more complex to implement and manage as compared to single-linked lists.
-
Use/Applications
-
-
- Doubly linked lists are commonly used in scenarios where bidirectional traversal or efficient insertion/deletion operations are required, such as in implementing certain data structures (e.g., deque, linked list-based stacks, and queues) or algorithms that involve frequent list manipulation.
-
(C) Circular linked list
Definition
-
-
- A circular linked list is one, which has no beginning and no end.
- A circular linked list is a linked list where all nodes are connected to form a circle.
-
Features
-
-
- There is no NULL pointer in its end node.
-
Advantages
-
-
- In this linked list, any node can be a starting point. We can traverse the whole list by starting from any point. We just need to stop when the first visited node is visited again to complete the traversing.
- Useful for the implementation of the queue because we don’t need to maintain two pointers for front and rear if we use a circular linked list. We can maintain a pointer to the last inserted node and the front can always be obtained as next of last.
- Circular lists are useful in applications to repeatedly go around the list. For example, when multiple applications are running on a PC, it is common for the operating system to put the running applications on a list and then cycle through them, giving each of them a slice of time to execute, and then making them wait while the CPU is given to another application.
- Circular Doubly Linked Lists are used for the implementation of advanced data structures like the Fibonacci Heap.
-
Disadvantages
-
-
- Circular linked list is comparatively complex.
- Reverse processing in this is comparatively complex.
-
Types
-
-
- There are two types of circular linked lists – (a) Single Circular Linked List and (b)Double Circular Linked List
-
(a) Single Circular Linked List
Definition
-
-
- A single linked list can be made a circular linked list by simply storing the address of the very first node in the link field of the last node.
-
Features
-
- Simple structure with circular facility.
- Circular movement is possible.
Syntax/Declaration
struct tag-name
{
Datatype member 1;
Datatype member 2;
.
.
.
Datatype member n;
struct tag-name *pointer;
};
Example
struct student
{
int rollno;
char stuname[30];
float fee;
struct student *ptr;
};
Advantages
-
-
- Comparatively simple structure.
- Fast searching occurs.
-
Disadvantages
-
-
- Only forward movement occurs in it (not backward).
- No terminator nodes were found.
-
(b) Double Circular Linked List
Definition
-
- A circular double-linked list is one, that has both the successor pointer and predecessor pointer in a circular manner.
Features
-
- The circular doubly linked list doesn’t contain a NULL pointer in any of the nodes.
- The first node of this list contains the address of the last node in its previous/back pointer.
- The last node of this list contains the address of the first node of the list.
Syntax/Declaration
struct tag-name
{
struct tag-name *pointer1;
Datatype member 1;
Datatype member 2;
.
.
.
Datatype member n;
struct tag-name *pointer2;
};
Example
struct student
{
struct student *back;
int rollno;
char stuname[30];
float fee;
struct student *next;
};
Advantages
-
- Fast searching occurs.
- Forward and backward movement occurs easily.
Disadvantages
-
- It Consumes more memory comparatively in its structure.
- Comparatively complex in structure.
0 Comments