Creating a Doubly Linked List in Data Structure

A doubly linked list is a type of data structure that consists of a sequence of nodes. Each node contains two pointers, one pointing to the previous node and the other pointing to the next node in the sequence. This allows for easy traversal in both directions.

To create a doubly linked list, you need to define a class or structure that represents each node. Each node should have three components: the data it holds, a pointer to the previous node, and a pointer to the next node. Here’s an example implementation in C++:

## Implementation

“`cpp

class Node {

public:

int data;

Node* prev;

Node* next;

};

“`

In this implementation, we define a class called `Node` which has three member variables: `data`, `prev`, and `next`. The `data` variable represents the value stored in each node. The `prev` pointer points to the previous node, while the `next` pointer points to the next node.

## Creating Nodes

To create nodes for our doubly linked list, we can use dynamic memory allocation. Here’s an example function that creates a new node with a given value:

“`cpp

Node* createNode(int value) {

Node* newNode = new Node();

newNode->data = value;

newNode->prev = nullptr;

newNode->next = nullptr;

return newNode;

}

“`

In this function, we allocate memory for a new node using the `new` keyword. We then assign the given value to the `data` member variable of the new node and set both `prev` and `next` pointers to nullptr.

## Building the Doubly Linked List

Once we have our nodes ready, we can start building our doubly linked list by connecting them together. We need to maintain two pointers: `head`, which points to the first node in the list, and `tail`, which points to the last node.

Here’s an example function that adds a new node to the end of the list:

“`cpp

void addNode(Node** head, Node** tail, int value) {

Node* newNode = createNode(value);

if (*head == nullptr) {

*head = newNode;

*tail = newNode;

} else {

(*tail)->next = newNode;

newNode->prev = *tail;

*tail = newNode;

}

}

“`

In this function, we first create a new node using the `createNode` function. If the list is empty (i.e., `head` is nullptr), we make both `head` and `tail` point to the new node.

Otherwise, we update the next pointer of the current tail to point to the new node and update the prev pointer of the new node to point back to the current tail. Finally, we update `tail` to point to the new node.

## Traversing the Doubly Linked List

To traverse a doubly linked list, you can start from either end and follow the next or prev pointers accordingly. Here’s an example function that prints all elements in a doubly linked list:

“`cpp

void printList(Node* head) {

while (head != nullptr) {

cout << head->data << " ";
head = head->next;

}

}

“`

In this function, we start from `head` and print its data value. Then we move on to the next node by updating `head` to point to its next pointer. We repeat this process until we reach nullptr.

## Conclusion

Congratulations! You’ve successfully learned how to create a doubly linked list in the data structure.

Doubly linked lists are versatile data structures that allow for easy traversal in both directions. With proper implementation and usage, they can be powerful tools in various applications.

Remember to always handle memory management properly by deallocating memory when you’re done with the list to prevent memory leaks.