Linked List Implementation in C#

1. Introduction

A LinkedList is a linear data structure where elements are stored in nodes. Each node contains a data part and a reference/link to the next node in the sequence. A linked list can be seen as a chain of nodes, where each node points to the next one in line. Linked lists offer advantages over traditional arrays in certain scenarios, such as dynamic size, ease of insertion/deletion, and efficient memory utilization.

2. Implementation Steps

1. Define a Node class to represent individual items in the linked list.

2. Create a LinkedList 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 linked list with these operations.

3. Implementation in C#

using System;
public class Node {
    public int Value;
    public Node Next;
    public Node(int value) {
        this.Value = value;
        this.Next = null;
    }
}
public class LinkedList {
    private Node head;
    // Add node to the end of the list
    public void Append(int value) {
        if (head == null) {
            head = new Node(value);
            return;
        }
        Node current = head;
        while (current.Next != null) {
            current = current.Next;
        }
        current.Next = new Node(value);
    }
    // Add node to the beginning of the list
    public void Prepend(int value) {
        Node newHead = new Node(value);
        newHead.Next = head;
        head = newHead;
    }
    // Remove the node with a specific value
    public void DeleteWithValue(int value) {
        if (head == null) return;
        if (head.Value == value) {
            head = head.Next;
            return;
        }
        Node current = head;
        while (current.Next != null) {
            if (current.Next.Value == value) {
                current.Next = current.Next.Next;
                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() {
        LinkedList list = new LinkedList();
        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. We define a Node class with two properties: Value and Next. The Value holds the data, and Next is a reference to the subsequent node.

2. The LinkedList class manages nodes and provides methods for common operations.

3. The Append method adds a node to the end of the list. If the list is empty, it sets the head to the new node.

4. The Prepend method adds a node to the start of the list.

5. The DeleteWithValue method removes the node with a specific value from the list.

6. The PrintList method iterates over the nodes and displays their values.

7. In the Program class, we test our linked list's functionality by appending, prepending, deleting, and printing the list.

This provides a foundational understanding of the LinkedList implementation in C#.