Doubly Linked List Implementation in C#

1. Introduction

A DoublyLinkedList is a more advanced form of the basic linked list where each node not only has a link to the next node but also a link to the previous node. This allows for bidirectional traversing, which means you can move both forwards and backward through the list. While this adds complexity to certain operations, it can make other operations like deletion or insertion at both ends more efficient.

2. Implementation Steps

1. Define a Node class to represent individual items in the doubly linked list. Each node will have three attributes: Value, Next, and Previous.

2. Create a DoublyLinkedList class to manage the nodes and operations.

3. Implement basic operations:

- Append: Add a node to the end of the list.

- Prepend: Add a node to the beginning of the list.

- DeleteWithValue: Remove the node with a specific value.

- PrintList: Display the contents of the list.

4. Test the doubly linked list with these operations.

3. Implementation in C#

using System;
public class Node {
    public int Value;
    public Node Next;
    public Node Previous;
    public Node(int value) {
        this.Value = value;
        this.Next = null;
        this.Previous = null;
    }
}
public class DoublyLinkedList {
    private Node head;
    private Node tail;
    // Add node to the end of the list
    public void Append(int value) {
        Node newNode = new Node(value);
        if (tail == null) {
            head = tail = newNode;
        } else {
            tail.Next = newNode;
            newNode.Previous = tail;
            tail = newNode;
        }
    }
    // Add node to the beginning of the list
    public void Prepend(int value) {
        Node newNode = new Node(value);
        if (head == null) {
            head = tail = newNode;
        } else {
            head.Previous = newNode;
            newNode.Next = head;
            head = newNode;
        }
    }
    // Remove the node with a specific value
    public void DeleteWithValue(int value) {
        Node current = head;
        while (current != null) {
            if (current.Value == value) {
                if (current.Previous != null) {
                    current.Previous.Next = current.Next;
                } else {
                    head = current.Next;
                }
                if (current.Next != null) {
                    current.Next.Previous = current.Previous;
                } else {
                    tail = current.Previous;
                }
                return;
            }
            current = current.Next;
        }
    }
    // Display the contents of the list
    public void PrintList() {
        Node current = head;
        while (current != null) {
            Console.WriteLine(current.Value);
            current = current.Next;
        }
    }
}
public class Program {
    public static void Main() {
        DoublyLinkedList list = new DoublyLinkedList();
        list.Append(1);
        list.Append(2);
        list.Append(3);
        list.Prepend(0);
        list.DeleteWithValue(2);
        list.PrintList();  // Should print: 0 1 3
    }
}

Output:

0
1
3

Explanation:

1. The Node class has an additional attribute, Previous, which links to the node before it.

2. The DoublyLinkedList class has both a head and a tail pointer.

3. The Append method is modified to ensure that the new node's Previous attribute points to the previous tail, and then the tail is updated to point to the new node.

4. Similarly, the Prepend method is updated to ensure the new node's Next attribute points to the previous head, and then the head is updated to point to the new node.

5. The DeleteWithValue method is a bit more complex because we need to ensure the Next and Previous attributes of the surrounding nodes are updated correctly.

6. The PrintList method remains largely unchanged from the singly linked list version but traverses the list in a forward direction.

With this implementation, we have the ability to traverse the list in both directions, providing more flexibility and efficiency in certain operations.