[C#] Linear Data Structures

📋 This is my note-taking from what I learned in the course!

• https://learning.oreilly.com/library/view/professional-c-7/9781119449270/c10.xhtml#head-2-88

Linear Data Structures

This guide covers various linear data structures, including arrays, array lists, and linked lists (both singly and doubly linked). These structures are essential for organizing and managing data efficiently in programming.

Static Linear Data Structures

Arrays

Definition

An array is a sequenced collection of variables of the same type. Each element in an array is accessed by an index.

Characteristics

• Fixed size: The size of the array is defined when it is created.
• Elements are stored in contiguous memory locations.

Declaring Arrays

First Way

int[] numbers = { 1, 2, 3, 4, 5 };

Second Way

int[] numbers = new int[5]; // Creates an array of size 5

Adding and Removing Elements

Adding an Element

To add an element at index i, you need to shift all elements from index i onwards to the right.

void AddElement(int[] array, int index, int element) {
    for (int i = array.Length - 1; i > index; i--) {
        array[i] = array[i - 1];
    }
    array[index] = element;
}

Removing an Element

To remove an element at index i, you need to shift all elements from index i + 1 to the left.

void RemoveElement(int[] array, int index) {
    for (int i = index; i < array.Length - 1; i++) {
        array[i] = array[i + 1];
    }
    array[array.Length - 1] = 0; // Optional: Clear the last element
}

ArrayList

ArrayLists in C# are dynamic arrays that can grow as needed.

ArrayList arrayList = new ArrayList();
arrayList.Add(1);
arrayList.Add("Hello");
arrayList.Remove(1);

Reference: ArrayList Class

List

List<T> is a generic collection designed for strongly-typed data and provides dynamic resizing.

List<int> list = new List<int>();
list.Add(1);
list.Add(2);
list.Remove(1);

Reference: [List Class](https://learn.microsoft.com/en-us/dotnet/api/system.collections.generic.list-1?view=net-8.0)

SortedList

A SortedList maintains a collection of key/value pairs that are sorted by the keys.

SortedList<int, string> sortedList = new SortedList<int, string>();
sortedList.Add(1, "One");
sortedList.Add(2, "Two");

Reference: SortedList Class

Dynamic Linear Data Structures

Singly Linked Lists

Definition

A singly linked list is a sequence of nodes where each node points to the next node in the sequence.

Operations

• Insert at Head

  public void insertAtHead(int data) {
      Node newNode = new Node(data);
      newNode.next = head;
      head = newNode;
  }
  

• Insert at Tail

  public void insertAtTail(int data) {
      Node newNode = new Node(data);
      if (head == null) {
          head = newNode;
      } else {
          Node current = head;
          while (current.next != null) {
              current = current.next;
          }
          current.next = newNode;
      }
  }
  

• Remove at Head

  public void removeAtHead() {
      if (head != null) {
          head = head.next;
      }
  }
  

• Remove at Tail Removing at the tail is not efficient for singly linked lists because there is no direct reference to the previous node.

  public void removeAtTail() {
      if (head == null) return;
      if (head.next == null) {
          head = null;
          return;
      }
      Node current = head;
      while (current.next.next != null) {
          current = current.next;
      }
      current.next = null;
  }
  

Doubly Linked Lists

Definition

A doubly linked list is a sequence of nodes where each node points to both its previous and next nodes.

Operations

• Insertion

  public void insert(Node previous, Node newNode, Node next) {
      previous.next = newNode;
      newNode.previous = previous;
      newNode.next = next;
      if (next != null) {
          next.previous = newNode;
      }
  }
  

• Deletion

  public void delete(Node node) {
      if (node.previous != null) {
          node.previous.next = node.next;
      }
      if (node.next != null) {
          node.next.previous = node.previous;
      }
  }
  

LinkedList in .NET

LinkedList<T> is a doubly linked list implementation in .NET.

LinkedList<int> linkedList = new LinkedList<int>();
linkedList.AddFirst(1);
linkedList.AddLast(2);
linkedList.RemoveFirst();
linkedList.RemoveLast();

Reference: [LinkedList Class](https://learn.microsoft.com/en-us/dotnet/api/system.collections.generic.linkedlist-1?view=net-8.0)

---

Back to Top

See other articles in Category CS