Linked List Design

Posted by Jim Scott on Stack Overflow See other posts from Stack Overflow or by Jim Scott
Published on 2010-04-12T04:43:15Z Indexed on 2010/04/12 5:03 UTC
Read the original article Hit count: 394

Filed under:

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)  

© Stack Overflow or respective owner

Related posts about c#