CLinkedList Class

Basic Linked list class with some interfaces implemented to work with WPF UI elements

CLinkedList class, is a custom C# generic class implementing basic Doubly linked list operations with some extra features for ease of use and better integration with other .Net classes especially for WPF UI elements. We chose the class to be generic so the list elements can be of any type chosen by the end user

CLinkedList Class

Namespace: TASLibrary.CustomDataStructures Assembly: TASLibrary.dll

Represents a doubly linked list.

CLinkedList.cs

public class CLinkedList<T> : 
ICollection<T>, 
IEquatable<CLinkedList<T>>, 
ISerializable, 
IDeserializationCallback, 
INotifyCollectionChanged 
where T : class {}

Type Parameters

T Specifies the element type of the linked list.

Implements

ICollection<T>, IEquatable<T>, ISerializable, IDeserializationCallback, INotifyCollectionChanged

Remarks

CLinkedList is a general-purpose linked list. It supports enumerators and implements the ICollection interface, consistent with other collection classes in the .NET Framework.

CLinkedList provides separate nodes of type CNode, so insertion and removal are O(1) operations.

The list maintains an internal count, getting the Count property is an O(1) operation.

Each node in a CLinkedList object is of the type CNode. Because the CLinkedList is doubly linked, each node points forward to the Next node and backward to the Previous node.

If the CLinkedList is empty, the First and Last properties contain null.

The CLinkedList class does not support chaining, splitting, cycles, or other features that can leave the list in an inconsistent state.

Class Members

Private Members:

• _head: The first node in the list of type CNode<T>.

private CNode<T> _head;

• _tail: The last node in the list of type CNode<T>.

private CNode<T> _tail;

• _count: Nodes count in the list of type int.

private int _count;

• _siInfo; Serialization data used while deserialization of the Type SerializationInfo.

private SerializationInfo _siInfo;

Public Members

• First: Gets the first element in the list of type T.

public T First { get { return _head.Data; } }

• Last: Gets the last element in the list of type T.

public T Last { get { return _tail.Data; } }

• Count: Gets the number of nodes actually contained in the list.

public int Count { get { return _count; } }

• IsReadOnly; Determines if the class is read only or not of type bool.

public bool IsReadOnly { get { return false; } }

Private Methods

AddNodeToEmptyList(CNode<T>)

Adds the specified node to an empty list.

private void AddNodeToEmptyList(CNode<T> newNode)
{
    Debug.Assert(
        _head == null && _count == 0, 
        "Can't use this function if the list is not empty!");
    newNode.Next = null;
    newNode.Prev = null;
    _head = newNode;
    _tail = _head;
}

InternalFind(int)

Finds the node at the specified index.

private CNode<T> InternalFind(int index)
{
    if (index >= _count)
    {
        throw new ArgumentOutOfRangeException();
    }
    CNode<T> currentNode;
    if (index < _count / 2)
    {
        currentNode = _head;
        for (int i = 0; i < index; i++)
        {
            currentNode = currentNode.Next;
        }
        return currentNode;
    }
    else
    {
        currentNode = _tail;
        for (int i = 0; i < _count - 1 - index; i++)
        {
            currentNode = currentNode.Prev;
        }
        return currentNode;
    }
}

InternalFind(T)

Finds the node that contains the same specified data.

private CNode<T> InternalFind(T data)
{
    CNode<T> tempNode = _head;
    int index = 0;
    EqualityComparer<T> c = EqualityComparer<T>.Default;
    if (tempNode != null)
    {
        if (data != null)
        {
            do
            {
                tempNode.Index = index;
                if (c.Equals(tempNode.Data, data))
                {
                    return tempNode;
                }
                tempNode = tempNode.Next;
                index++;
            } while (tempNode != null);
        }
    }
    return null;
}

CreateList(T[])

Initializes the list after deserialization from the specified array.

private void CreateList(T[] array)
{
    for (int i = 0; i < array.Length; i++)
    {
        AddLast(array[i]);
    }
}

Public Methods

this[int]

Gets or sets the element at the specified index.

public T this[int index]
{
    get
    {
        return InternalFind(index).Data;
    }
    set
    {
        index += 1;
        InternalFind(index).Data = value;
    }
}

AddLast(T)

Adds a new node containing the specified value at the end of the list.

public void AddLast(T data)
{
    CNode<T> newNode = new CNode<T>(data);
    if (_head == null)
    {
        AddNodeToEmptyList(newNode);
    }
    else
    {
        _tail.Next = newNode;
        newNode.Prev = _tail;
        _tail = newNode;
    }
    _count++;
    if (CollectionChanged != null)
    {
        CollectionChanged(this, 
        new NotifyCollectionChangedEventArgs(
        NotifyCollectionChangedAction.Add,
        newNode.Data));
    }
}

AddFirst(T)

Adds a new node containing the specified value at the start of the list.

public void AddFirst(T data)
{
    CNode<T> newNode = new CNode<T>(data);
    if (_head == null)
    {
        AddNodeToEmptyList(newNode);
    }
    else
    {
        newNode.Next = _head;
        _head.Prev = newNode;
        _head = newNode;
    }
    _count++;
    if (CollectionChanged != null)
    {
        CollectionChanged(this, 
        new NotifyCollectionChangedEventArgs(
        NotifyCollectionChangedAction.Add, 
        newNode.Data));
    }
}

RemoveLast()

Removes the node at the end of the list.

public void RemoveLast()
{
    if (_head == null)
    {
        throw new InvalidOperationException(
        "Can't remove the first element in an empty list!");
    }
    else
    {
        CNode<T> tNode = _tail;
        if (_count == 1)
        {
            _head = null;
            _tail = null;
        }
        else
        {
            _tail = _tail.Prev;
            _tail.Next = null;
        }                                
        if (CollectionChanged != null)
        {
            CollectionChanged(this, 
            new NotifyCollectionChangedEventArgs(
            NotifyCollectionChangedAction.Remove, 
            tNode.Data, 
            _count-1));
        }
        tNode.DeleteNode();
        _count--;
    }
}

RemoveFirst()

Removes the node at the start of the list.

public void RemoveFirst()
{
    if (_head == null)
    {
        throw new InvalidOperationException(
        "Can't remove the first element in an empty list!");
    }
    else
    {
        CNode<T> tNode = _head;
        if (_count == 1)
        {
            _head = null;
            _tail = null;
        }
        else
        {
            _head = _head.Next;
            _head.Prev = null;
        }                                
        if (CollectionChanged != null)
        {
            CollectionChanged(this, 
            new NotifyCollectionChangedEventArgs(
            NotifyCollectionChangedAction.Remove, 
            tNode.Data,
            0));
        }
        tNode.DeleteNode();
        _count--;
    }
}

Remove(T)

Removes the first occurrence of the specified value from the list.

public bool Remove(T data)
{
    CNode<T> tempNode = InternalFind(data);
    if(tempNode == null)
    {
        return false;
    }
    else
    {
        if(tempNode == _head)
        {
            RemoveFirst();
        }
        else if(tempNode == _tail)
        {
            RemoveLast();
        }
        else
        {
            tempNode.Prev.Next = tempNode.Next;
            tempNode.Next.Prev = tempNode.Prev;
            if (CollectionChanged != null)
            {
                CollectionChanged(this, 
                new NotifyCollectionChangedEventArgs(
                NotifyCollectionChangedAction.Remove, 
                tempNode.Data, 
                tempNode.Index));
            }
            tempNode.DeleteNode();
            _count--;
        }
        return true;
    }
}

RemoveAt(int)

Removes the node at the specified index from the list.

public void RemoveAt(int index)
{
    if (index == 0)
    {
        RemoveFirst();
    }
    else if(index == _count -1)
    {
        RemoveLast();
    }
    else
    {
        CNode<T> tempNode = InternalFind(index);
        tempNode.Prev.Next = tempNode.Next;
        tempNode.Next.Prev = tempNode.Prev;
        if (CollectionChanged != null)
        {
            CollectionChanged(this, 
            new NotifyCollectionChangedEventArgs(
            NotifyCollectionChangedAction.Remove, 
            tempNode.Data, 
            index));
        }
        tempNode.DeleteNode();
        _count--;
    }            
}

Clear()

Removes all nodes from the list.

public void Clear()
{
    CNode<T> currentNode = _head;
    while (currentNode != null)
    {
        CNode<T> tNode = currentNode;
        currentNode = currentNode.Next;
        tNode.DeleteNode();
    }
    _head = null;
    _tail = null;
    _count = 0;
}

Find(T)

Finds the first node that contains the specified value.

public T Find(T data)
{
    if(_head != null)
    {
        return InternalFind(data).Data;
    }
    return default(T);            
}

Find(Predicate<T>)

Finds the first node that matches the specified predicate.

public T Find(Predicate<T> match)
{
    if (match == null)
    {
        throw new ArgumentNullException();
    }
    CNode<T> currentNode = _head; 
    while (currentNode != null)
    {
        if (match(currentNode.Data))
        {
            return currentNode.Data;
        }
        currentNode = currentNode.Next;
    }
    return default(T);
}

FindAll(Predicate<T>)

Finds all the nodes that match the specified predicate.

public CLinkedList<T> FindAll(Predicate<T> match)
{
    if (match == null)
    {
        throw new ArgumentNullException();
    }
    CLinkedList<T> results = new CLinkedList<T>();
    CNode<T> currentNode = _head;
    while (currentNode != null)
    {
        if (match(currentNode.Data))
        {
            results.AddLast(currentNode.Data);
        }
        currentNode = currentNode.Next;
    }

    return results;
}

ToString()

Returns a string that represents the current object. (Override)

public override string ToString()
{            
    StringBuilder sb = new StringBuilder();
    sb.AppendLine("");
    sb.AppendLine($"{typeof(T).Name} List's Information:");
    sb.AppendLine("-----------------------");
    CNode<T> currentNode = _head;
    int i = 1;
    if (currentNode != null)
    {
        do
        {
            sb.Append($"{i}th {currentNode.Data}");
            currentNode = currentNode.Next;
            i++;
        } while (currentNode != null);
    }            
    return sb.ToString();
}

ToString(string)

Returns a string that represents the current object with the list name inserted to it.

public string ToString(string listName)
{
    StringBuilder sb = new StringBuilder();
    sb.AppendLine($"{listName} List's Information:");
    sb.AppendLine("-----------------------");
    CNode<T> currentNode = _head;
    int i = 1;
    if (currentNode != null)
    {
        do
        {
            sb.Append($"{i}th {currentNode.Data}");
            currentNode = currentNode.Next;
            i++;
        } while (currentNode != null);
    }
    return sb.ToString();
}

ICollection<T>

Defines methods to manipulate generic collections.

GetEnumerator()

Returns an enumerator that iterates through the linked list as a collection.

public IEnumerator<T> GetEnumerator()
{
    CNode<T> currentNode = _head;
    while (currentNode != null)
    {
        yield return currentNode.Data;
        currentNode = currentNode.Next;
    }
}
        
IEnumerator IEnumerable.GetEnumerator()
{
    return GetEnumerator();
}

Add()

Adds an item at the end of the list.

public void Add(T data)
{
    AddLast(data);
}

CopyTo(T[], int)

Copies the entire list to a compatible one-dimensional Array, starting at the specified index of the target array.

public void CopyTo(T[] array, int arrayIndex)
{
    CNode<T> currentNode = _head;
    if (currentNode != null)
    {
        do
        {
            array[arrayIndex++] = currentNode.Data;
            currentNode = currentNode.Next;
        } while (currentNode != null);
    }
}

Contains(T)

Checks if a given element exists in the list.

public bool Contains(T data)
{
    return Find(data) != null;
}

IEquatable<T>

Defines a generalized method that a value type or class implements to create a type-specific method for determining equality of instances.

Equals(CLinkedList<T>)

Determines whether the specified object is equal to the current object.

public bool Equals(CLinkedList<T> other)
{
    if (Object.ReferenceEquals(other, null))
    {
        return false;
    }
    if (Object.ReferenceEquals(this, other))
    {
        return true;
    }
    if (this.GetType() != other.GetType())
    {
        return false;
    }
    return (_head == other._head && _count == other._count);
}

Equals(CLinkedList<T>)

Determines whether the specified object is equal to the current object. (Override)

public override bool Equals(object obj)
{
    return this.Equals(obj as CLinkedList<T>);
}

GetHashCode

Serves as the default hash function.

public override int GetHashCode()
        {
            int hashCode = -33681659;
            hashCode = hashCode * -1521134295 + EqualityComparer<CNode<T>>.Default.GetHashCode(_head);
            hashCode = hashCode * -1521134295 + EqualityComparer<CNode<T>>.Default.GetHashCode(_tail);
            hashCode = hashCode * -1521134295 + _count.GetHashCode();
            return hashCode;
        }

==(CLinkedList<T>, CLinkedList<T>)

Determines whether the first object is equal to the other object.

public static bool operator ==(CLinkedList<T> lhs, CLinkedList<T> rhs)
{

    if (Object.ReferenceEquals(lhs, null))
    {
        if (Object.ReferenceEquals(rhs, null))
        {
            return true;
        }
        return false;
    }
    return lhs.Equals(rhs);
}

!=(CLinkedList<T>, CLinkedList<T>)

Determines whether the first object is not equal to the other object.

public static bool operator !=(CLinkedList<T> lhs, CLinkedList<T> rhs)
{
    return !(lhs == rhs);
}

ISerializable

Allows an object to control its own serialization and deserialization.

GetObjectData(SerializationInfo, StreamingContext)

Implements the ISerializable interface and returns the data needed to serialize the list instance.

public void GetObjectData(SerializationInfo info, StreamingContext context)
{
    if (info == null)
    {
        throw new ArgumentNullException("info");
    }
    if (_count != 0)
    {
        T[] array = new T[_count];
        CopyTo(array, 0);                
        info.AddValue("values", array, typeof(T[]));
    }
}

CLinkedList<>(SerializationInfo, StreamingContext)

Initializes a new instance of the CLinkedList class that is serializable with the specified SerializationInfo and StreamingContext.

public CLinkedList(SerializationInfo info, StreamingContext context)
{
    siInfo = info;
}

IDeserializationCallback

Indicates that a class is to be notified when deserialization of the entire object graph has been completed.

OnDeserialization(object sender)

Implements the ISerializable interface and raises the deserialization event when the deserialization is complete.

public void OnDeserialization(object sender)
{
    T[] array = (T[])siInfo.GetValue("values", typeof(T[]));
    CreateList(array);
}

INotifyCollectionChanged

Notifies listeners of dynamic changes, such as when an item is added and removed or the whole list is cleared.

CollectionChanged

Occurs when the collection changes.

public event NotifyCollectionChangedEventHandler CollectionChanged;