Ever since I graduated I’ve been employed as a .NET consultant. When applying for jobs (whether it’s at a consultancy firm or as a representative of your firm getting interviewed by a client) there is often a technical interview. Next to the fun object-orientation questions we all love so much (explain polymorphism, data abstraction, inheritance, Liskov’s substitution principle,…), there were sometimes these little exercises they used to test your approach to problem solving or to see how you react to a very unfamiliar problem. These questions can take different forms. You’ve got you’re here-is-a-piece-of-code-and-tell-me-what-the-output-is-questions, mathematical problems, writing code,…Even brain-teasers can be a part of the interview.
In the “writing code” department you can be asked to write well known data structures yourself (e.g.: write your own linked list/binary tree), write an algorithm (sorting algorithm,search algorithm, reversing collections,…). The meaning of this series is to discuss some of these questions, find out where the pitfalls are and see what side-questions might be added to the exercise.
So let’s get to it! As a first exercise, let’s look at an implementation of a linked list. In the .NET Framework, you can find a linked list in the System.Collections.Generic library.
For our basic implementation we need a Node-class where we can hold the references for the previous and the next item in the list. We’ll immediately keep references to both the next and the previous node as we’ll notice that it might be handy to navigate through the list. This is already a more complex version of a linked list (since the most simplistic version only holds the reference to the next node).
1: public class Node
2: {
3: private Node prevNode;
4: private Node nxtNode;
5: private string strValue;
6:
7: public Node(Node prevNode, Node nxtNode, string stringValue)
8: {
9: this.prevNode = prevNode;
10: this.nxtNode = nxtNode;
11: this.strValue = stringValue;
12: }
13:
14: public Node PrevNode
15: {
16: get { return this.prevNode; }
17: set { this.prevNode = value; }
18: }
19:
20: public Node NxtNode
21: {
22: get { return this.nxtNode; }
23: set { this.nxtNode = value; }
24: }
25:
26: public string StringValue
27: {
28: get { return this.strValue; }
29: set { this.strValue = value; }
30: }
31:
32: public void Delete()
33: {
34: this.prevNode.nxtNode = this.nxtNode;
35: this.nxtNode.prevNode = this.prevNode;
36: }
37: }
This is a basic node-class. As a value I chose a string, but of course, that can be anything you want. This node is what we’ll use to create our list. We’ll have a list-object that contains the first node, and of course, since each node points to the next one in the list, the list-object will contain all the methods to navigate through the list.
1: public class LinkedList
2: {
3: public LinkedList(string stringValue)
4: {
5: nCurrent = new Node(null, null, stringValue);
6: nCurrent.NxtNode = null;
7: nCurrent.PrevNode = null;
8: }
9:
10: int iCount = 1;
11: int iCurrent = 0;
12: Node nCurrent;
13:
14: public int Count
15: {
16: get{return this.iCount; }
17: }
18:
19: public Node CurrentNode
20: {
21: get{return this.nCurrent;}
22: }
23:
24: public Node CurrentNodeIndex
25: {
26: get{return this.nCurrent;}
27: }
28:
29: public void AddNode(string strValue)
30: {
31: if (nCurrent.NxtNode == null)
32: {
33: nCurrent.NxtNode = nCurrent;
34: nCurrent = new Node(nCurrent, null, strValue);
35: }
36: else
37: {
38: nCurrent.NxtNode = nCurrent;
39: nCurrent = new Node(nCurrent, nCurrent.NxtNode, strValue);
40: }
41: iCount++;
42: iCurrent++;
43: }
44:
45: public void ToNext()
46: {
47: Node tmpNode = null;
48:
49: if (nCurrent.NxtNode == null)
50: {
51: throw new Exception("there is no next node!");
52: }
53: else
54: {
55: tmpNode = nCurrent;
56: nCurrent = nCurrent.NxtNode;
57: nCurrent.PrevNode = tmpNode;
58: iCurrent++;
59: }
60: }
61:
62: public void ToPrevious()
63: {
64: Node tmpNode = null;
65:
66: if (nCurrent.PrevNode == null)
67: {
68: throw new Exception("there is no previous node!");
69: }
70: else
71: {
72: tmpNode = nCurrent;
73: nCurrent = nCurrent.PrevNode;
74: nCurrent.NxtNode = tmpNode;
75: iCurrent--;
76: }
77: }
78:
79: public void GoTo(int index)
80: {
81: while (iCurrent != index)
82: {
83: if (iCurrent < index)
84: {
85: ToNext();
86: }
87: else if (iCurrent > index)
88: {
89: ToPrevious();
90: }
91: }
92: }
93:
94: public void First()
95: {
96: while (nCurrent.PrevNode != null)
97: {
98: ToPrevious();
99: }
100: }
101: }
Now you can instantiate the list. The constructor also requires a string value to define your first element in the list. Then you’ll find the methods to navigate through the list. And the nCurrent-property of the Linked List will contain the node where you navigated to.
A possible variation you might get asked is a circular linked list. This means that the last element you add (which points to null) actually should point to the first element in the list. For a full theoretical explanation I refer to wikipedia.