{"id":11418,"date":"2022-12-26T11:52:34","date_gmt":"2022-12-26T11:52:34","guid":{"rendered":"https:\/\/www.prepbytes.com\/blog\/?p=11418"},"modified":"2023-06-08T12:30:15","modified_gmt":"2023-06-08T12:30:15","slug":"doubly-linked-list-program-in-c","status":"publish","type":"post","link":"https:\/\/prepbytes.com\/blog\/doubly-linked-list-program-in-c\/","title":{"rendered":"Doubly Linked List Program in C"},"content":{"rendered":"

\"\"<\/p>\n

We shall explore the definition and operation of a doubly linked list in this post. In addition, we will implement a doubly linked list program in C with a thorough description, a dry run, and an algorithm, and at the conclusion of the article, we will analyze the time and space costs associated with such a program.<\/p>\n

What is a Doubly Linked List?<\/h2>\n

A doubly linked list is a data structure that consists of a sequence of elements, where each element contains a reference to the previous and next element in the sequence. In contrast to a singly linked list, which only has a reference to the next element, a doubly linked list allows traversal in both directions.
\nEach element in a doubly linked list, commonly called a "node," contains two pointers or references: one pointing to the previous node and another pointing to the next node. The first and last nodes of the list have their previous and next pointers set to null or a special value to indicate the beginning and end of the list.<\/p>\n

\"\"<\/p>\n

The memory representation to the above mentioned illustration of a linked list with the colorized data denoting the information a doubly linked list holds i.e. previous address, next address and the data:-<\/p>\n\n\n\n\n\n\n\n\n\n\n\n
Node<\/th>\nPrevious<\/th>\nNext<\/th>\nData<\/th>\n<\/tr>\n<\/thead>\n
2004<\/td>\nNULL<\/td>\n2008<\/td>\n5<\/td>\n<\/tr>\n
2008<\/td>\n2004<\/td>\n2012<\/td>\n4<\/td>\n<\/tr>\n
2012<\/td>\n2008<\/td>\n2016<\/td>\n35<\/td>\n<\/tr>\n
2016<\/td>\n2012<\/td>\n2020<\/td>\n2<\/td>\n<\/tr>\n
2020<\/td>\n2016<\/td>\n2024<\/td>\n1<\/td>\n<\/tr>\n
2024<\/td>\n2020<\/td>\n2028<\/td>\n0<\/td>\n<\/tr>\n
2028<\/td>\n2024<\/td>\nNULL<\/td>\n0<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n

There are different operations performed on a doubly linked which are demonstrated as:<\/p>\n

    \n
  • Traversal – Forward\/Backward<\/li>\n
  • Insert – Start\/End\/Position<\/li>\n
  • Delete<\/li>\n<\/ul>\n

    In this article, we are going to create doubly linked list program in c that covers all of the operations mentioned. A doubly linked is created with the help of self-referential structure in C programming language.<\/p>\n

    struct Node {\n    int data;\n    struct Node* next;\n    struct Node* prev;\n};<\/code><\/pre>\n
    The traversal to linked list requires the head node which is traversed until the head becomes zero. Though, in doubly linked list, traversal can be performed both the ways, courtesy of previous pointer.<\/p>\n
    Insert at Start – Doubly Linked List Program in C<\/h3>\n
    Lets look at each operation that is going to be a subpart of the doubly linked list program in C. Firstly, we have the dry run, algorithm, code and analysis for the insert at the start operation.<\/p>\n
    Step To Insert at Start of Doubly Linked List
    \nWe assign the head to the ptr node and lets suppose that we have a newly created node temp containing the value want to link at start, the next of temp is addressed to ptr and the previous of ptr is addressed to temp. Finally, the head is updated to the temp (newly created node) with its previous being NULL.<\/p>\n
    Algorithm<\/strong><\/p>\n
    Step 1: IF head = NULL\n            Exit\nStep 2: SET ptr = head\nStep 3: SET temp -> data = data\nStep 4: SET temp -> prev = NULL\nStep 5: SET temp -> next = ptr\nStep 6 SET ptr->prev = temp\nStep 6: SET temp -> prev = NULL\nStep 7: SET head = temp\nStep 8: EXIT<\/code><\/pre>\n
    \t\t\t\t\t\t