Linked List Design
- by Jim Scott
The other day in a local .NET group I attend the following question came up: "Is it a valid interview question to ask about Linked Lists when hiring someone for a .NET development position?"
Not having a computer sciense degree and being a self taught developer my response was that I did not feel it was appropriate as I in 5 years of developer with .NET had never been exposed to linked lists and did not hear any compeling reason for a use for one.
However the person commented that it is a very common interview question so I decided when I left that I would do some reasearch on linked lists and see what I might be missing.
I have read a number of posts on stack overflow and various google searches and decided the best way to learn about them was to write my own .NET classes to see how they worked from the inside out.
Here is my class structure
Single Linked List
Constructor
public SingleLinkedList(object value)
Public Properties
public bool IsTail
public bool IsHead
public object Value
public int Index
public int Count
private fields not exposed to a property
private SingleNode firstNode;
private SingleNode lastNode;
private SingleNode currentNode;
Methods
public void MoveToFirst()
public void MoveToLast()
public void Next()
public void MoveTo(int index)
public void Add(object value)
public void InsertAt(int index, object value)
public void Remove(object value)
public void RemoveAt(int index)
Questions I have:
What are typical methods you would expect in a linked list?
What is typical behaviour when adding new records? For example if I have 4 nodes and I am currently positioned in the second node and perform Add() should it be added after or before the current node? Or should it be added to the end of the list?
Some of the designs I have seen explaining things seem to expose outside of the LinkedList class the Node object. In my design you simply add, get, remove values and know nothing about any node object.
Should the Head and Tail be placeholder objects that are only used to define the head/tail of the list?
I require my Linked List be instantiated with a value which creates the first node of the list which is essentially the head and tail of the list. Would you change that ?
What should the rules be when it comes to removing nodes. Should someone be able to remove all nodes?
Here is my Double Linked List
Constructor
public DoubleLinkedList(object value)
Properties
public bool IsHead
public bool IsTail
public object Value
public int Index
public int Count
Private fields not exposed via property
private DoubleNode currentNode;
Methods
public void AddFirst(object value)
public void AddLast(object value)
public void AddBefore(object existingValue, object value)
public void AddAfter(object existingValue, object value)
public void Add(int index, object value)
public void Add(object value)
public void Remove(int index)
public void Next()
public void Previous()
public void MoveTo(int index)
