Linked list design
The other day in the local .NET group I come to the following question: "Is the proper interview question a Linked Lists question when hiring someone for a .NET development position?"
With no computer science degree and being a self-taught developer, my response was that I didn't feel it was appropriate as I after 5 years developing with .NET have never been exposed to linked lists and have not heard any good reason to use for one.
However, the person commented that this is a very common interview question, so I figured when I leave, I will do some re-examination of linked lists and see what I might be missing.
I read several posts about Stack Overflow and various google searches, and decided that the best way to learn about them is to write my own .NET classes to see how they work 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 the typical methods you would expect in a linked list?
What is the typical behavior when adding new records? For example, if I have 4 nodes and I am currently placed in the second node and execute 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 constructs I've seen explaining things seem to expose the node object outside of the LinkedList class. In my project, you just add, get, remove values and don't know anything about any node object.
Should Head and Tail be placeholder objects that are only used to define the head / tail of the list?
I require my linked list to be created with a value that creates the first node of the list, which is essentially the head and tail of the list. Would you change that?
What should be the rules when it comes to deleting nodes. Should someone remove all nodes?
Here is my double link 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);
source to share
It looks like your LinkedList remembers where it is and can then perform various actions accordingly. I would prefer a simpler design like below (it's 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 separate or a doubly linked list. Some projects have a link to the end of the list, so it's faster to add files at the end, but for simplicity, skip this. It is still a (conditionally 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. Of course, the point of learning such a thing is not to implement the tree when you go to work. It helps you justify the cost (in space and time) of what you are doing, or convince yourself if a piece of code is correct or not.
If you're curious, there is a course with MIT videos here , or you can check out this course from Stanford, which includes less math. Hope you enjoy this.
Good luck :)
source to share
My advice would be to just mimic a reasonably thoughtful C ++ implementation. One such implementation is the SGI Linked List . Please note that the page I am linking to is not code, it is a list of signature and definitions that you like.
Linked lists are somewhat too low for the average C # programmer to really think about them in normal terms. Usually, a basic understanding of how they work and the complexity of the various operations involved is sufficient, for example. combining two linked lists can be done in O (1) time.
Note. Take a look at the Model section on the SGI page, as each analytic list is a "model" to provide guarantees of complexity.
source to share
There are many ways to implement a Linked List, but they ultimately boil down to a series of objects, each with a pointer to the next object. The question then becomes "What other functionality 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 about "what methods do I need?" and was more worried about how to reason about the structure of the linked list enough to implement whatever arbitrary method the interviewer asked.
However, if you are looking for more realistic scenarios like Linked Lists, I would suggest you take a look at the Java Linked List and .NET Linked List API designs .
source to share
What are the typical methods you would expect in a linked list?
Add (), AddAt (), Remove (), RemoveAt (), ElementAtTop (), ElementAtLast (), ElementAt (),
What is the typical behavior when adding new records? For example, if I have 4 nodes and I am currently the second node and do the Add () command if it is 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 how you implement the linked list. Let's say if you are using STACK with a linked list, this method will add a new element (node) at the top position. If you are using QUEUE using a linked list then the item will be added at the last position.
Some of the constructs I've seen explaining things seem to be outside the LinkedList class of the node object. In my design, you just add, get, remove values and know nothing about any node object.
If head and tail are placeholder objects that are only used to define the head / tail of the list?
I think YES . They would be useful for moving or changing a linked list.
I need my linked list instance with a value that 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 you understand you. But I will also implement it in the same way.
What should be the rules for when this happens? to remove nodes. Should someone be able to delete all nodes?
Remove (): Same explanation as Add (). Follow the links in Add ().
source to share