Skip to content
Tutorials Center
My learning

Topics

Lesson 181 of 182 ยท Practice and Review

Data Structures from Scratch in C#

Build a singly linked list and a binary search tree from scratch in C#, then solve classic array problems - rotation, duplicate removal and binary search in a rotated array - with tested code.

The .NET base library gives you List<T>, Dictionary<TKey,TValue> and SortedSet<T>, so in daily work you almost never write your own linked list. But building one by hand is the best way to learn how references, nodes and recursion really work, and these exact exercises are favorites in interviews. This lesson builds a singly linked list and a binary search tree from scratch, then solves three classic array problems: rotating an array, removing duplicates in place, and searching a rotated sorted array.

Every program here runs in the editor. Read the code first, predict the output, then run it. For the underlying theory of collections see choosing collections; for recursion see recursion in C#.

A singly linked list

A linked list is a chain of nodes. Each node stores a value and a reference to the next node. The list only remembers the first node, called the head. Adding at the front is cheap; reaching the n-th item means walking the chain.

We will write one class with these operations:

  • AddLast and AddFirst
  • Reverse: flip the direction of all links
  • NthFromEnd(n): the n-th node counting from the end, in a single pass
  • RemoveDuplicates: drop repeated values from a sorted list
  • Merge: combine two sorted lists into one sorted list

Two techniques do most of the work. Reversing keeps three references (previous, current, next) and re-points each link as it walks. Two pointers (a "fast" and "slow" or a "leader" and a "follower") solve the n-th-from-the-end problem without knowing the length: move the leader n steps ahead, then move both until the leader falls off the end.

C# Linked list: reverse, nth from end, duplicates, merge

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with Console.ReadLine()), it gets the next line from this box.

AddLast walks the whole chain each time, so building a list of n items that way costs O(n squared). A real implementation also keeps a _tail reference (the .NET LinkedList<T> does) so that AddLast is O(1). Reverse and RemoveDuplicates run in O(n) time and O(1) extra space, because they only re-point existing links.

When a linked-list problem has special cases for the head, use a dummy node in front of the real head, as Merge does. The special case disappears because the head is now just another Next.

A binary search tree

A binary search tree (BST) is a tree where each node has at most two children, and for every node, all values in its left subtree are smaller and all values in its right subtree are larger. That ordering makes search fast: at each node you discard half of the remaining tree, as long as the tree is balanced.

C# Binary search tree: insert, find, traverse, height

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with Console.ReadLine()), it gets the next line from this box.

An in-order traversal (left, node, right) of a BST visits the values in sorted order, which is why the first output line is sorted even though you inserted the numbers in a different order. Insert and Contains take O(h) time, where h is the height. For a balanced tree that is about log2(n), but the last line shows the danger: inserting already sorted data builds a chain of height n. Production code uses self-balancing trees; in .NET, SortedSet<T> and SortedDictionary<TKey,TValue> are red-black trees (see sorted collections).

The tree uses an iterator with yield return for the traversal. Iterators and yield explains how the compiler turns that recursion into a lazy sequence.

Rotating an array

Problem: rotate an array of n items to the left by k positions, in place and without a second array. [1,2,3,4,5,6,7] rotated left by 3 becomes [4,5,6,7,1,2,3].

The elegant solution is the reversal algorithm: reverse the first k items, reverse the remaining n-k items, then reverse the whole array. Each element moves a constant number of times, so it is O(n) time and O(1) space.

Always take k % n first, because rotating by n is the same as not rotating at all, and rotating by more than n wraps around.

Removing duplicates in place

Problem: a sorted array contains repeats. Move the unique values to the front, return how many there are, and do not allocate a new array.

Use two indexes: write marks where the next unique value goes, and read scans ahead. Whenever array[read] differs from array[write - 1], copy it forward.

Searching a rotated sorted array

Problem: a sorted array of distinct values was rotated at an unknown pivot, giving something like [15,18,2,3,6,12]. Find the index of a target in O(log n).

Plain binary search fails because the whole array is no longer sorted. The key observation: when you cut the array at the middle, at least one half is still sorted. Check which half is sorted, check whether the target lies inside that half's range, and keep that half or discard it.

C# Rotation, in-place dedup and rotated binary search

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with Console.ReadLine()), it gets the next line from this box.

The last search prints -1 for 7, which means "not found", the same convention as Array.IndexOf. The rotated search keeps the O(log n) speed of ordinary binary search because each loop throws away half of the range.

Testing your own data structures

Hand-written structures are easy to get subtly wrong, so test the awkward cases: an empty list, a single node, a target at either end, all-equal values, and k larger than the array. The testing basics lesson shows how to turn such checks into repeatable unit tests.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. In a singly linked list you keep only the head. What is the time cost of reaching the 100th node?

    Nodes are not stored contiguously, so there is no indexing. You walk from the head following Next links.
  2. 2. How does the two-pointer technique find the n-th node from the end in one pass?

    When the leader falls off the end, the follower is exactly n nodes behind it, so it stands on the n-th node from the end.
  3. 3. What does an in-order traversal of a binary search tree produce?

    Visiting left subtree, node, then right subtree yields ascending order because of the BST ordering rule.
  4. 4. Which sequence rotates [1,2,3,4,5] left by 2 using the reversal algorithm?

    [2,1] + [5,4,3] gives [2,1,5,4,3]; reversing everything gives [3,4,5,1,2], the left rotation by 2.
  5. 5. Why does binary search still work on a rotated sorted array?

    Comparing a[lo] with a[mid] shows which half is sorted; a range check on that half decides where the target can be.

Summary

  • A linked list is nodes joined by references; reversal re-points links with previous, current and next.
  • The two-pointer technique and a dummy head node remove special cases from list problems.
  • A BST keeps smaller values on the left and larger on the right; in-order traversal is sorted, and search is O(height).
  • Rotate arrays in place with three reversals, remove sorted duplicates with a read and a write index, and search a rotated array by finding the sorted half.
  • In real code prefer List<T>, LinkedList<T> and SortedSet<T>; write your own to learn, or when a structure truly does not exist.

Next: more practice in advanced exercises, or revisit interview questions.