Hi folks, I'm Basappa Hadapad employee of LUXOFT India. Here I would like to provide a brief knowledge about Data structure(singly linked list and doubly linked list).
Introduction:
Data structures are specialized means of organizing and string data in computers in such a way that we can perform operations on it in more efficiently. Not only for arranging the data it is used for retrieving, processing, and storing the data.
Needs of data structure:
1) It will take very less time.
2) It will save the size of memory.
3) Representation of data is easy.
4) We can access the large database easily.
There are different types of data structure some types mentioned below:
1)Linear data structure
i)Dynamic data structure
-Linked list
-Stack
-Queue
ii)static data structure
-Array
2)Non-linear data structure
-Tree
-Graph
• Linear data structure: In this data structure data elements are arranged linearly or sequential, each element is attached to the next adjacent and previous elements, this called as linear data structure.
Examples: stack, array, linked list, queue etc.
• Static data structure: memory size of the static data structure is fixed. In static data structure we can access the elements easily.
Example: array.
• Dynamic data structure: memory size of the dynamic data structure is not fixed. It will update randomly during runtime.
Examples: Linked list, stack, queue.
• Non-linear data structure: in non-linear data structure data elements are not placed linearly or sequentially are called as nonlinear data structure. I this data structure we cannot traverse all elements in single run.
Examples: graphs, trees
Linked list:
1.Single linked list
2.Double linked list
3.circular linked list
1.Single linked list:
Example: Insert new node at beginning:
• Check the given node is exist or not.
-If does not exist,
-Stop the process.
• If given node is exists,
-Create the element to be insert as new node.
-Change the next pointer of the given node to new node.
-Shift the original next pointer of the given node to next pointer of the new node.
Program: Insert the node beginning of the linked list
• Create first node of the linked list link to the new node.
• Remove the head from the first node of the linked list.
• Create a new node and make it as head of the linked list.
#include < iostream >
using namespace std;
struct Node {
int data;
struct Node next;
};
struct Node head = NULL;
void insert_first(int new_data) {
struct Node* new_node = (struct Node*) malloc(sizeof(struct Node));
new_node->data = new_data;
new_node->next = head;
head = new_node;
}
void PrintLinkedList() {
struct Node* ptr;
ptr = head;
cout<<"The linked list is: ";
while (ptr != NULL) {
cout<< ptr->data <<" ";
ptr = ptr->next;
}
}
int main() {
insert_first(3);
insert_first(1);
insert_first(7);
insert_first(2);
PrintLinkedList();
return 0;
}
In the above program linked list node is formed by structure Node. This structure has the data and pointer. Data will store the information and for pointing the next node pointer will be used.
insert_first() : In this function new nodes will be created at the beginning of the linked list, here allocates the memory dynamically for new node.
PrintLinkedList(): In this function will print all nodes.
Characteristics of singly linked list:
• Each node holds a single reference and single value to the next node in the list.
• Singly linked list has head, this is the reference to the first node of the list.
• Each node holds the address of next node in the list and nodes are not store in contiguous block of memory.
• In singly linked list for access the elements require s traversing the list from the head to desired node.
• We can’t access the specific node directly from the memory.
Application of single linked list:
• Memory management: we can used to implement memory pools, in which memory is deallocated and allocated needed.
• Database indexing: In databases can use for implementing the linked lists, allowing for fast deletion and insertion operation.
• Representing polynomials and sparse matrices: singly linked lists can be used to efficiently represent sparse matrices and polynomials, where the most elements are zero.
• Operating systems: In operating system singly linked lists are using for tasks such as managing system resources and scheduling processes.
Advantages of singly linked list:
• Dynamic memory allocation: Singly linked list allocate the memory dynamically, size of the list will change at runtime as elements are removes or added.
• Cache friendliness: In Singly linked lists, nodes will be stored in separate cache lines, improve the performance and reduce the cache misses.
• Space-efficient: Singly linked list is space-efficient, only need to store a reference to next node in each element.
Disadvantages of Singly Linked Lists:
• Poor random-access performance: In singly linked lists required traversing the list from head to desired node for accessing the elements from the list, so it will make the operation slow.
• Increased memory overhead: Singly linked lists need additional memory for storing the pointers to next node in each element.
• Vulnerability to data loss: Singly linked list main disadvantage is data loss if a node’s next pointer is corrupted or loss, there is no another way to traverse the list and access the elements.
• Not suitable for parallel processing: For the parallel processing singly, linked lists are not suitable, for updating node need to access the next pointer, it’s not easy to done in parallel environment.
• Backward traversing not possible: backward traversing does not support in singly linked list.
Doubly linked list:
It’s a type of data structure and it’s a made up of nodes. Each node has three parts, first part Pointer to the previous node, second part will store the information and third part will pointer to the next node.
Every doubly linked list has head and tail. Head will pointer to the first node of the linked list if there are no nodes it will store the NULL and tail is the last node of the linked list and it will point to the last node of the linked list.
Example: Insert the node beginning of the doubly linked list
#include < iostream >
using namespace std;
struct Node {
int data;
struct Node prev;
struct Node *next;
};
struct Node head = NULL;
void insert_beginning(int newdata) {
struct Node* newnode = (struct Node*) malloc(sizeof(struct Node));
newnode->data = newdata;
newnode->prev = NULL;
newnode->next = head;
if(head != NULL)
head->prev = newnode ;
head = newnode;
}
void printDoublyLinkedList() {
struct Node* ptr;
ptr = head;
cout<<"The doubly linked list is: ";
while(ptr != NULL) {
cout<< ptr->data <<" ";
ptr = ptr->next;
}
}
int main() {
insert_beginning(3);
insert_beginning(1);
insert_beginning(7);
insert_beginning(2);
printDoublyLinkedList();
return 0;
}
In the above program doubly linked list is formed by structure Node. This structure has prev, data and next. prev variable used for pointer to the previous node, data is used for store the information and next is used for pointer to the next node.
insert_beginning() : In this function new nodes will be created at the beginning of the linked list, here allocates the memory dynamically for new node.
printDoublyLinkedList (): In this function will print all nodes.
Conclusion:
Data structure will help to developers for organize, manage and store the information. Computer data structures described by relationships between the items, the operations supported by the actual values of the items, and structure. Developers often create new algorithms and data structures for an application, but many structures built into the main programming languages
Top comments (0)