Linked List Design_问答_开发者_运维开发者技术经验分享

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 science degree and being a self taught developer my response was that I did not feel it was appropriate as I in 5 years of developing with .NET had never been exposed to linked lists and did not hear any compelling 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 开发者_JS百科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);

It looks like your LinkedList remembers where it is at, then can perform various actions accordingly. I'd prefer a simpler design like below (this is Java, though):

class LinkedList<T> {
    private int size;
    private Node<T> head;

    public int size();
    public T get(int index);
    public void add(T newObject);
    public void remove(int index);
    public void remove(Object object);
}

class Node<T> {
    T value;
    Node<T> next;
    Node<T> prev; // only applicable for doubly linked list
}

So the interface is the same, whether it's a singly or doubly linked list. Some designs have a reference to the end of the list, so it's faster to append stuff at the end, but for simplicity, let's skip that. It's still a (conventionally accepted) linked list.

Basic data structures and algorithms are very useful. People often don't believe/understand that things they don't know are actually useful. Sure, the point of learning such a thing is not to implement a tree when you go to work. It helps you to reason about the cost (in space and time) of what you do, or convince yourself whether a piece of code is correct or not.

If you're interested, there is a course with videos from MIT here, or you can check out this course from Stanford, which involves less math. I hope you find these fun to learn.

Good luck :)

My advice would be to just mimic a reasonably well-thought out implementation from C++. One such implementation is SGI's Linked List. Note that the page I refer to is not code, it's a list of signatures and definitions much like the one you provided.

Linked Lists are somewhat too low level for the average C# programmer to need to actually be thinking about them in normal circumstances. Usually, a basic understanding of how they work and the complexity of the different operations involved is sufficient, e.g. concatenating two linked lists can be done in O(1) time.

Note: Take note of the "Model of" section of the SGI page, since each think lists are a "model of" provides complexity guarantees.

There are a large number of ways to implement a Linked List, but they ultimately all boil down to a series of objects each with a pointer to the next object. The question then is "What other features do I require to accomplish what I need with a Linked List data structure?"

In the context of an interview question, I would be less concerned with "what methods do I need?" and more concerned with how to reason about the Linked List's structure enough to implement any arbitrary method that an interviewer would ask.

However, if you are looking for more real world type scenarios of Linked Lists, I would suggest you look at the API design of the Java Linked List, and the .Net Linked List implementations.

What are typical methods you would expect in a linked list?

Add(), AddAt(), Remove(), RemoveAt(), ElementAtTop(), ElementAtLast(), ElementAt(),

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?

Add(): The functionality of this method depends on the way you are implementing the linked list. Say, if you are implementing STACK using linked list, this method would add the new element (node) at TOP position. While if your are implementing QUEUE using linked list then the element will be added to last position.

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 think YES. They would be useful to traverse or reverse the linked 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 ?

I'm not sure if I understood you. But I would also implement it in the same way.