Singly linked list RemoveBefore() method

Question

I am trying to implement a singly linked list. What is the most optimal way of implementing a RemoveBefore(ListNode) method?

I have done this:

1. Check if node being removed is the head. If so, return.
2. Check if there are two nodes and node being removed is the tail. Then set head and tail as the same. Old tail will be automatically disposed.
3. If there are more than 2 nodes and the above 2 conditions are not satisfied track current node, child node and grandchild node.
4. If grandchild node is the requested node the make current node point to grandchild node. Child node will be disposed.

namespace DataStructures.Lists { public interface ISinglyLinkedNode<T> where T : IComparable<T> { T Data { get; set; } ISinglyLinkedNode<T> Next { get; set; } } public interface ISinglyLinkedList<T> where T : IComparable<T> { ISinglyLinkedNode<T> Head { get; } ISinglyLinkedNode<T> Tail { get; } void Add(ISinglyLinkedNode<T> Data); void AddHead(ISinglyLinkedNode<T> Data); void AddTail(ISinglyLinkedNode<T> Data); void RemoveHead(); void RemoveTail(); void AddAt(int Index, ISinglyLinkedNode<T> Data); void InsertAfter(ISinglyLinkedNode<T> Node, T Data); void InsertBefore(ISinglyLinkedNode<T> Node, T Data); ISinglyLinkedNode<T> GetAt(int Index); void RemoveAt(int Index); void RemoveAfter(ISinglyLinkedNode<T> Node); void RemoveBefore(ISinglyLinkedNode<T> Node); void Remove(ISinglyLinkedNode<T> Node); void ReverseList(); } public interface IPrintLinkedList { void PrintLinkedList(); } /// <summary> /// Definition of a Singly linked node. This node has a data slot and a single pointer slot pointing to the next /// singly linked node. /// </summary> /// <typeparam name="T"></typeparam> public class SinglyLinkedNode<T> : IDisposable, IComparable<SinglyLinkedNode<T>>, ISinglyLinkedNode<T> where T : IComparable<T> { private T _data; private ISinglyLinkedNode<T> _next; public SinglyLinkedNode() { _data = default(T); _next = null; } public SinglyLinkedNode(T data) { _data = data; _next = null; } public T Data { get { return _data; } set { _data = value; } } public ISinglyLinkedNode<T> Next { get { return _next; } set { _next = value; } } int IComparable<SinglyLinkedNode<T>>.CompareTo(SinglyLinkedNode<T> other) { if (other == null) return -1; return this.Data.CompareTo(other.Data); } #region IDisposable Support private bool disposedValue = false; // To detect redundant calls protected virtual void Dispose(bool disposing) { if (!disposedValue) { if (disposing) { IDisposable disposable = _data as IDisposable; if (disposable != null) disposable.Dispose(); } disposedValue = true; } } public void Dispose() { Dispose(true); } #endregion } /// <summary> /// Implements ISinglyLinkedList and defines a singly linked list /// </summary> /// <typeparam name="T">Template type</typeparam> public class SinglyLinkedList<T> : ISinglyLinkedList<T>, IPrintLinkedList, IEnumerable<T> where T : IComparable<T> { private ISinglyLinkedNode<T> _head; private ISinglyLinkedNode<T> _tail; public SinglyLinkedList() { _head = null; _tail = null; } #region ISinglyLinkedList implementation ISinglyLinkedNode<T> ISinglyLinkedList<T>.Head { get { return _head; } } ISinglyLinkedNode<T> ISinglyLinkedList<T>.Tail { get { return _tail; } } void ISinglyLinkedList<T>.Add(ISinglyLinkedNode<T> Data) { (this as ISinglyLinkedList<T>).AddHead(Data); } void ISinglyLinkedList<T>.AddAt(int Index, ISinglyLinkedNode<T> Data) { throw new NotImplementedException(); } void ISinglyLinkedList<T>.AddHead(ISinglyLinkedNode<T> Data) { Data.Next = _head; _head = Data; } void ISinglyLinkedList<T>.AddTail(ISinglyLinkedNode<T> Data) { _tail.Next = Data; _tail = Data; } ISinglyLinkedNode<T> ISinglyLinkedList<T>.GetAt(int Index) { if (Index < 0) return new SinglyLinkedNode<T>(); ISinglyLinkedNode<T> Temp = _head; for (int i = 0; i < Index - 1; i++) { Temp = Temp.Next; } return Temp; } void ISinglyLinkedList<T>.Remove(ISinglyLinkedNode<T> Node) { //empty linked list if (_head == null) return; for (ISinglyLinkedNode<T> current = _head, prev = null; current != null; prev = current, current = current.Next) { if (object.Equals(current.Data, Node.Data)) { prev.Next = current.Next; break; } } } void ISinglyLinkedList<T>.RemoveAfter(ISinglyLinkedNode<T> Node) { Node.Next = Node.Next.Next; } void ISinglyLinkedList<T>.RemoveAt(int Index) { (this as ISinglyLinkedList<T>).Remove((this as ISinglyLinkedList<T>).GetAt(Index)); } void ISinglyLinkedList<T>.RemoveBefore(ISinglyLinkedNode<T> Node) { //cannot remove before head if (object.Equals(Node.Data, _head.Data)) return; //if we need to remove the node before tail then make head and tail the same if (object.Equals(Node.Data, _tail.Data)) { _head = _tail; (_tail as IDisposable).Dispose(); } for (ISinglyLinkedNode<T> currentnode = _head, child = null, grandchild = null; currentnode != null; currentnode = currentnode.Next) { child = currentnode.Next; grandchild = child.Next; if (object.Equals(Node.Data, grandchild.Data)) { currentnode.Next = grandchild; break; } } } void ISinglyLinkedList<T>.RemoveHead() { lock (_head) { lock (_head.Next) { _head = _head.Next; } } } void ISinglyLinkedList<T>.RemoveTail() { ISinglyLinkedNode<T> currentnode = _head; //check if there is only one node. Remove head then if (_head.Next == null) { _head = null; return; } //if there are only two nodes set heads next to null to remove tail if (_head.Next != null && _head.Next.Next == null) { _head.Next = null; return; } for (ISinglyLinkedNode<T> current = _head, child = current.Next, grandchild = child.Next; current != null; current = current.Next) { } } #endregion #region IEnumerable implementation IEnumerator IEnumerable.GetEnumerator() { return new SinglyLinkedListEnumerator<T>(); } IEnumerator<T> IEnumerable<T>.GetEnumerator() { return new SinglyLinkedListEnumerator<T>(); } #endregion void IPrintLinkedList.PrintLinkedList() { PrintNode(_head); } void PrintNode(ISinglyLinkedNode<T> Node) { if (Node == null) { Debug.Write(" | " + "NULL" + " | " + "\n"); return; } Debug.Write(" | " + Node.Data + " | " + "-->"); PrintNode(Node.Next); } void ISinglyLinkedList<T>.InsertAfter(ISinglyLinkedNode<T> Node, T Data) { throw new NotImplementedException(); } void ISinglyLinkedList<T>.InsertBefore(ISinglyLinkedNode<T> Node, T Data) { throw new NotImplementedException(); } void ISinglyLinkedList<T>.ReverseList() { // < __ < __ < __ __: reversedPart: head // (__)__ __ __ //head : current: > > > ISinglyLinkedNode<T> reversedPart = null; ISinglyLinkedNode<T> current = _head; while (current != null) { ISinglyLinkedNode<T> next = current.Next; current.Next = reversedPart; reversedPart = current; current = next; } _head = reversedPart; } internal class SinglyLinkedListEnumerator<T> : IEnumerator<T> { public T Current { get { throw new NotImplementedException(); } } object IEnumerator.Current { get { throw new NotImplementedException(); } } public void Dispose() { throw new NotImplementedException(); } public bool MoveNext() { throw new NotImplementedException(); } public void Reset() { throw new NotImplementedException(); } } } } 

Answer 1

Simplifying RemoveBefore

Don't over-complicate things with unnecessary special cases. You already have a loop for looping through all the nodes. Just use that, with a few changes:

Instead of keeping track of decendents (child and grandchild) of the current node (currentnode), keep track of its ancestors (parent and grandparent). Then when currentnode matches the input node (Node):

• parent is the node to be removed
• grandparent needs to have its next reference updated
• currentnode is what grandparent.next should be set to

There are a couple special cases:

• parent is null =>Node has no parent (is _head) => nothing needs to be removed
• grandparent is null =>parent is _head =>currentnode becomes the new _head
• We fall out of the loop without finding Node => nothing needs to be done

Here's how this translates to code:

void ISinglyLinkedList<T>.RemoveBefore(ISinglyLinkedNode<T> Node) { for (ISinglyLinkedNode<T> currentnode = _head, parent = null, grandparent = null; currentnode != null; currentnode = currentnode.Next) { if (object.Equals(Node.Data, grandchild.Data)) { if(parent == null) { // currentnode is _head => do nothing break; } else if(grandparent == null) { // parent is _head => currentnode becomes new _head _head = currentnode break; } else { // We are removing parent => grandparent.Next becomes currentnode grandparent.Next = currentnode break; } } // Update parent and grandparent for next iteration grandparent = parent; parent = currentnode; } } 

This is a good start, but the logic is still a little more complex than it needs to be. For one thing, since every block ends with a break, we can move those outside. But we also don't really need to do anything when parent is null. Here's how I would probably write the logic:

// If parent is null, we don't need to do anything if(parent != null) { if(grandparent == null) { // parent is _head => currentnode becomes _head _head = currentnode; } else { // We are removing parent => grandparent.Next becomes currentnode grandparent.Next = currentnode; } } // In any case, we're done! break; 

Other Suggestions

Here are a few other suggestions:

• Consider having RemoveBefore return itself at the end instead of being a void function. This allows users to chain method invocations together in a "fluid" pattern. For example: list.RemoveBefore(a).RemoveBefore(b). The same goes for other methods as well.

• You are comparing nodes for equality based on their Data properties, but RemoveBefore takes a node as a parameter. This could be confusing, because the user when the user passes in one node, the code could match an entirely different node (i.e., if the same data is stored in two different locations in the list). I suggest doing one of the following:

  • Compare nodes based on identity (i.e., pointer equality). This will allow users to remove nodes at precise locations, regardless of the data stored in the list.
  • Instead of RemoveBefore taking a node parameter, have it take the data stored in the node instead. This way, it's clear that comparison is based on the data, not the position of a particular node.

  Of course, you could implement both ideas in separate methods. The same also goes for other methods as well.

Answer 2

Reinventing the wheel is a useful learning exercise. However, it's worth considering what has gone before you and the environment that you're performing the exercise in. .Net provides some common interfaces that generic collection classes can implement to help them fit into the existing landscape. Consider implementing some of ICollection<T>, IEnumerable<T>, IEnumerable, ICollection, IReadOnlyCollection<T>.

This will help your list to fit in with the existing framework (so that for example collection extension methods and linq support are more straightforward). It will also help you decide on some of the methods that your class should consider implementing.

I think @Nathan has covered most points around your RemoveBefore method, which is what you were after the review for, however I'd consider throwing an exception if the provided item isn't in the list. There's also quite a lot that could be said about the rest of your code if you're looking for a full review (such as the mismatch between the locking in RemoveHead and the rest of the code).