## Fundamentals - Data Structures

### Summary

#### Theory

The singly-linked list is the most basic of all the linked data structures. A singly-linked list is simply a sequence of dynamically allocated objects, each of which refers to its successor in the list. Despite this simplicity, there are many possible implementations, some of which are shown in the figure below: A. B, C and D are variations of a singly-linked list:

• Linked list A is the most basic implementation where each element refers to its successor and the last element refers to null. One variable labelled Head points to the first item in the list and is used to keep track of the list. However, this implementation is inefficient when we want to add elements to both ends of the list. To add an element at the end (the tail), we need to traverse the entire list to locate the last element. Obviously, not very efficient.

• Linked list B is an improvement over A because it makes adding elements to the tail of the list much more efficient. Here we use a second variable called Tail which always refers to the last element in the list.

• Linked List C illustrates two common programming tricks:

1. The sentinel element is never used to hold data and is always present. It is used because it simplifies the programming of certain operations. For example, since there is always a sentinel standing guard, we never need to modify the Head variable.

2. Linked list C is a circular list. Instead of having the tail point to null to demarcate the last element in the list, the last element refers to the sentinel. The advantage of this trick is that insertion at the head, at the tail, or at an arbitrary location of the list are all identical operations (the first element follows the last element immediately).

• Linked list D is again a circular list, but this time the variable Tail refers to the last element in the list. And since this is a circular list, the first element follows the last element immediately, therefore, it is relatively simple to insert both at the head and at the tail of this list.

The following figure shows the empty list representation for each of the above implementations. Note that the sentinel is always present. Note that with a linked list there is no notion of an inherent limit on the number of items that can be placed in a linked list. Items can be added until memory is exhausted.

#### Implementation

The implementation that follows uses variation B since it supports append and prepend operations efficiently. The following figure illustrates the our singly-linked list scheme. There are two main classes:

1. Element class which is used to represent each element in the list. Element class has three fields  - list, value, and next.

2. LinkedList class which is the main data structure. A LinkedList instance contains 0 or more Elements. LinkedList class has two fields - Head and Tail. The following shows a complete implementation of a linked list using scheme B. When studying the code, it is crucial that you refer back to the diagrams above. Otherwise, understanding the code can be difficult:

// Represents a node for linked lists
public sealed class Element<T> where T : IEquatable<T>
{
#region Data members
// Note: declaring member variables private or protected is incorrect because then
// they cannot be accessed by SingleLinkedList class. Declaring them public is also
// incorrect because these members are not supposed to be accessed by any class except
// SinglyLinkedList. Therefore, the best solution is to declare them internal
internal T                   datum = default(T);       // get default value of generic type parameter T
internal Element<T>          next;
#endregion

#region Constructors
// Used to initialize member variables
public Element(SinglyLinkedList<T> container, T value, Element<T> nextElement)
{
list = container;
datum = value;
next = nextElement;
}
#endregion

#region Properties to expose data members
{
get { return list; }
}

internal T Value
{
get { return datum; }
}

internal Element<T> NextElement
{
get { return next; }
set { next = value; }
}
#endregion

#region public interface

// Inserts an element after the current element (identified by 'this')
public void InsertAfter(T oValue)
{
// To understand this: the next element pointed to by the current element
// should become the element that we wish to insert. Visualize the situation
// by drawing a linked list representation
next = new Element<T>(list, oValue, this.next);

// Check if we are inserting at the end
if (list.Tail == this)
list.Tail = next;
}

// Inserts an element before the current element (identified by 'this')
public void InsertBefore(T oValue)
{
// Create a new element whose next element is the current element. The following
// statement, does the above but it does not properly place the new element in the
// list. For example, which element in the list has this new element as its next
// element?
Element<T> eNew = new Element<T>(list, oValue, this);

// Check for boundary conditions: If current element (this) is the head, then the
// new element eNew should become the head (in other words, if Head points to the
// current element, then Head should be changed to point to the new element).
// Otherwise, it becomes necessary to traverse the linked list starting from the
// head to locate the element that must precede the new element
else
{
// Loop from the beginning until the element identified by 'this', i.e., the
// current element is located.
while (ePrevious != null && ePrevious.next != this)
ePrevious = ePrevious.next;

// Element was found. Now make its next element, the newly created element
ePrevious.next = eNew;
}
}
#endregion
}

// This class can be enumerated therefore, it inherits from IEnumerable<T>
public class SinglyLinkedList<T> :IEnumerable<T> where T : IEquatable<T>
{
#region Data members
// Data members are protected as this class could be specialized by a derived class. Again
// refer to linked list implementation to explain the functionality of 'head' and 'tail'
protected Element<T> head = null;    // always points to the first element in the list (unless empty)
protected Element<T> tail = null;    // always points to the last element in the list (unless empty)
#endregion

#region Constructors
// When the list is first created, it is empty. Therefore, fields head and tail
// are initially null as per their declaration. The constructor therefore, does nothing
{
/* Empty implementation */
}
#endregion

#region Properties
{
set { head = value; }
}

public Element<T> Tail
{
get { return tail; }
set { tail = value; }
}

public bool IsEmpty
{
get { return (head == null); }
}

// Retrieve value of the first element
public T FirstValue
{
get
{
if (IsEmpty)
throw new InvalidOperationException("List is empty");
}
}

// Retrieve value of the last element
public T LastValue
{
get
{
if (IsEmpty)
throw new InvalidOperationException("List is empty");
return tail.Value;
}
}
#endregion

#region Public methods

// Empties the contents of the cell. No need to traverse list and de-allocate each
// element as the GC will take care this. To clear the list, just re-initialize the
// head and tail to null.
public void Clear()
{
tail = null;
}

// Insert an element at the top of the list. The newly inserted element becomes
// the head of the list
public void Prepend(T oValue)
{
// Create a new element. Because the element is required to be at the top of the list,
// the next element it should point to should be the current head
Element<T> e = new Element<T>(this, oValue, head);

// Recall the meaning of head and tail: head always points to the first
// element (unless empty). tail always points to the last element (unless
// empty).
// Now, if the list is initially empty, the new element is the only element
// (i.e., first and last element), hence head and tail both point to the new
// element (look at the structure diagram for B). If list is not empty, the
// new element is now the first element and head should point to the new
// first element. tail need not modified as it always points to the last element
// which is different from the first element.
if (IsEmpty)
{
tail = e;
}
else
{
}
}

// Insert an element at the bottom of the list. The newly inserted element becomes
// the tail of the list
public void Append(T oValue)
{
// Create a new element. Because the element is required to be at the bottom of the list,
// the next element it should point to should be null
Element<T> e = new Element<T>(this, oValue, null);

// Recall the meaning of head and tail: head always points to the first element (unless empty).
// tail always points to the last element (unless empty). Now,if the list is initially empty, the new
// element is the only element (i.e., first and last element), hence head and tail both point to the
// new element (look at the structure diagram for B). If list is not empty, the new element is now the
// last element and tail should point to the new last element. head need not modified as it always
// points to the first element which is different from the last element.
if (IsEmpty)
{
tail = e;
}
else
{
tail.NextElement = e;
tail= e;
}
}

// Copies the elements of of the given source list to the current list
{
// Check against self copy
if (source == this)
return;

// Not a self-copy. First, clear all the elements in the current list
this.Clear();

// Then copy elements one-by-one from the source list to the current list
// Note the for-loop structure for a linked list: the start condition is the
// head of the list, the end condition is null, and the next iterations points
// to the next element
for (Element<T> eCurrent = source.head; eCurrent != null; eCurrent = eCurrent.next )
{
this.Append(eCurrent.datum);
}
}

// Deletes a given element by doing a sequential search and simply omitting the element from
// the list
public void Delete(T oValue)
{
// If list is empty, throw an exception
if (IsEmpty)
throw new InvalidOperationException("The list is empty");

// Search sequentially for the element to be deleted. Note the syntax of the for loop
// used to iterate over the linked list
for (Element<T> eCurrent = this.head; eCurrent != null; eCurrent = eCurrent.next)
{
// Does the current item have the same value?
if (eCurrent.datum.Equals(oValue))
{
eElementToDelete = eCurrent;
break;
}
else
ePreviousElement = eCurrent;
}

// We have looped through the list. Now examine what we found
// If no item was found, through an exception
if (eElementToDelete == null)

// The following logic can be easily understood by looking at the linked list diagram
// (list B in Fundamentals - Data Structures)
// If item to delete is the head, set the next element as the head
else if (eElementToDelete == tail)
// If item to delete is the tail, set the previous item to be the tail
tail = ePreviousElement;
else
ePreviousElement.next = eElementToDelete.next;
}

// Returns the count of elements in the list
public int Count
{
get
{
int nCount = 0;
for (Element<T> e = head; e != null; e = e.next)
nCount++;
return nCount;
}
}
#endregion

#region IEnumerable<T> Members
public IEnumerator<T> GetEnumerator()
{
IEnumerator<T> e = (IEnumerator<T>)new SLLEnumerator<T>(this);
return e;
}

#region IEnumerable Members
System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator()
{
IEnumerator e = (IEnumerator)new SLLEnumerator<T>(this);
return e;
}
#endregion
}

// This is an enumerator class over a singly-linked list. This is a standard implementation
// of an enumerator class
public class SLLEnumerator<T> : IEnumerator where T: IEquatable<T>
{
private int nIndex = -1;
{
list = sll;
}

#region IEnumerator Members
public object Current
{
get
{
if (eCurrent == null)
throw new InvalidOperationException("Current position is null");
return eCurrent.datum;
}
}

public bool MoveNext()
{
if (eCurrent == null)
else
eCurrent = eCurrent.NextElement;
return (eCurrent != null);
}

public void Reset()
{
eCurrent = null;
}
#endregion
}

{
// Create an empty linked list
string strValue = string.Empty;
int nCount = 0;
Element<string> eCurrent = null;

// Invoke variouso operations
eCurrent = sll.Head;         // eCurrent = null since list is empty
nCount = sll.Count;          // 0 since list is empty

// Add some data and examine list (recall Append adds data to the bottom of the list
// and Prepend adds data to the top of the list)
sll.Append("A");             // A
sll.Append("B");             // A,B
sll.Prepend("C");            // C, A, B
sll.Append("D");             // C, A, B, D
nCount = sll.Count;          // 4
strValue = sll.Tail.Value;   // "D"

// Delete data and examine list
sll.Delete( "A" );          // "A" which is head is removed. B now becomes head
strValue = sll.Tail.Value;  // "D"
}

### Containers

A container is an object that contains within it other objects. When implementing a container such as a Stack, Queue or Deque, the first issue to be addressed is which foundational data structure should be used to hold the actual elements of the container. There are two foundational data structures - the array and the linked-list. The sections that followi present a linked-list based implementation as it much cleaner and more efficient than array-based implementations.

Typically, you would develop a container by developing a set of common interfaces that can be implemented according to the type of the container. The following uses the .NET model to explain how common interfaces can be used to implement different types of containers. The most basic container interface is ICollection<T>:

public interface ICollection<T> : IEnumerable<T>, IEnumerable
{
// Properties
int     Count { get; }

// Methods
void    Clear();
bool    Contains(T item );
void    CopyTo( T[] array, int arrayindex );
bool    Remove( T item );
}

ICollection<T> inherits from IEnumerable which means that any container implementing ICollection<T> will be an enumerable collection (i.e., elements of the container can be accessed via foreach C# keyword). The ICollection<T> interface is usually enough to implement containers that usually limit access to their members such as Queue and Stack.

Note that containers implementing ICollection<T> do not support access by index, i.e., accessing an element within the container using array syntax. To provide this support for containers, we can use IList<T> which derives from ICollection<T>. IList<T> represents a collection which can be accessed by index:

public interface IList<T> : ICollection<T>, IEnumerable<T>, IEnumerable
{
// Properties
T this[int nIndex] { get; set; }

// Methods
int    IndexOf(T item );
void   Insert(int Index, T item );
void   RemoveAt(int index);
}

First thing to note is that even though ICollection<T> inherits from IEnumerable<T> and IEnumerable, IList<T> declaration specifies IEnumerable<T> and IEnumerable as base interfaces. This technique (mentioned here) is known as interface re-implementation and allows IList<T> to re-implement these two base interfaces accordingly

Another interface that specializes ICollection is IDictionary<T> which represents a generic collection of key, value pairs.

### Stacks

Consider a pile of printed papers on your desk. Suppose you add papers only to the top of the pile and remove them only from the top of the pile. At any point in time, the top paper is the only visible paper. What you have here is a stack.

From an implementation perspective, a stack has only two methods to add/remove entries to the stack - Push to add an item (to the top) and Pop to remove an item (from the top). Typically, stacks have an additional method called Top that returns the top of the stack without actually removing the item.

The following presents an implementation of the Stack container based on a singly-linked list:

public interface IStack<T> : ICollection where T : IEquatable<T>
{
void     Push(T oValue);
T        Pop();
void     Clear();
T        Top { get; }
}

public class StackAsLinkedList<T> : IStack<T> where T :IEquatable<T>
{
// The linked list is used as the underlying data structure used to hold data

{
}

#region IStack<T> members
public void Push(T o)
{
list.Prepend(o);   // Add item to top of linked list (top of stack)
}

public T Pop()
{
// Check stack is not empty
if (list.IsEmpty)
throw new InvalidOperationException("stack is empty");

// Get item from top of linked list (top of stack)
T oTop = list.FirstValue;
list.Delete(oTop);
return oTop;
}

public void Clear()
{
list.Clear();
}

public T Top
{
get
{
if (list.IsEmpty)
throw new InvalidOperationException("stack is empty");

return list.FirstValue;
}
}
#endregion

#region ICollection Members
public void CopyTo(Array array, int index)
{
throw new Exception("The method or operation is not implemented.");
}

public int Count
{
get { return list.Count; }
}

public bool IsSynchronized
{
get { throw new Exception("The method or operation is not implemented."); }
}

public object SyncRoot
{
get { throw new Exception("The method or operation is not implemented."); }
}
#endregion

#region IEnumerable Members
public IEnumerator GetEnumerator()
{
return new SLLEnumerator<T>(list);
}
#endregion
}

{
// Create a stack and push data
intStack.Push(10);
intStack.Push(20);
intStack.Push(30);
intStack.Push(40);
intStack.Push(50);

// Invoke various operations on the stack
int nCount = intStack.Count;         // 5
int nTop = intStack.Top;             // 50
int nCurrent = intStack.Pop();       // 50
nTop = intStack.Top;                 // 40
nCount = intStack.Count;             // 4

// Iterate over stack
foreach (int n in intStack)
Trace.WriteLine(n);
}

### Queues

Consider customers waiting in line to be served. As customers arrive, they join the end of the line waiting to be served. When a customer is served, he/she leaves the beginning of the line and gets served. What you have here is a queue. A queue is used when activities must be done in a first-come first-served bases (in electronics a queue is known as FIFO - First-In First-Out)

From an implementation perspective, a queue has only two methods to add/remove entries to the queue - Enqueue to add an item (to the bottom) and Dequeue to remove an item (from the top). Typically, stacks have an additional method called Head that returns the top of the queue without actually removing the item.

The following presents an implementation of the queue container based on a singly-linked list:

public interface IQueue<T> : ICollection where T: IEquatable<T>
{
void Enqueue(T item);
T    Dequeue();
}

class QueueAsLinkedList<T> : IQueue<T> where T : IEquatable<T>
{
// The linked list is used as the underlying data structure used to hold data

{
}

#region IQueue<T> members
public void Enqueue(T o)
{
list.Append(o);
}

public T Dequeue()
{
// Check stack is not empty
if (list.IsEmpty)
throw new InvalidOperationException("stack is empty");

// Remove item from the top of the linked list
T oTop = list.FirstValue;
list.Delete(oTop);
return oTop;
}

public void Clear()
{
list.Clear();
}
{
get
{
if (list.IsEmpty)
throw new InvalidOperationException("stack is empty");

return list.FirstValue;
}
}
#endregion

#region ICollection Members
public void CopyTo(Array array, int index)
{
throw new Exception("The method or operation is not implemented.");
}

public int Count
{
get { return list.Count; }
}

public bool IsSynchronized
{
get { throw new Exception("The method or operation is not implemented."); }
}

public object SyncRoot
{
get { throw new Exception("The method or operation is not implemented."); }
}
#endregion

#region IEnumerable Members
public IEnumerator GetEnumerator()
{
return new SLLEnumerator<T>(list);
}
#endregion
}

{
q.Enqueue(10);         // 10
q.Enqueue(20);         // 10, 20
q.Enqueue(30);         // 10, 20, 30
q.Enqueue(40);         // 10, 20, 30, 40
q.Enqueue(50);         // 10, 20, 30, 40, 50

// Invoke various operations on the queue
int nCount = q.Count; // 5
int nTop = q.Head;    // 10
int n1 = q.Dequeue(); // 20, 30, 40, 50 (n1 = 10)
int n2 = q.Dequeue(); // 30, 40, 50 (n1 = 20)
q.Enqueue(60);        // 30, 40, 50, 60

foreach (int n in q)
Trace.WriteLine(n);
}

### Deques

Consider a deck of playing cards. Cards can be added/removed to/from the top of the deck. Cards can also be added/removed to/from the bottom of the deck. A deque can be considered as the general case in which items can be added/deleted from top and bottom. The word deque is derived from doubled-ended queue. Stacks and queues are just special cases in which items are restricted in where they can be added or removed.

From an implementation perspective, a deque has four methods to add/remove entries - EnqueueHead and EnqueueTail to add an item to either end of the deque, and DequeueHead and DequeueTail to remove an item from either end of the deque. Typically, deques have additional methods called Head and Tail to return the top/bottom of the deque without actually removing the item.

public interface IDeque<T> : ICollection where T: IEquatable<T>
{
void EnqueueTail(T item);
T    DequeueTail();
T    Tail { get; }
}

class DequeAsLinkedList<T> : IDeque<T> where T : IEquatable<T>
{
// The linked list is used as the underlying data structure used to hold data

{
}

#region IDeque<T> members
{
list.Prepend(o);
}
public void EnqueueTail(T o)
{
list.Append(o);
}

{
// Check stack is not empty
if (list.IsEmpty)
throw new InvalidOperationException("stack is empty");

T oTop = list.FirstValue;
list.Delete(oTop);
return oTop;
}
public T DequeueTail()
{
// Check stack is not empty
if (list.IsEmpty)
throw new InvalidOperationException("stack is empty");

T oBottom = list.LastValue;
list.Delete(oBottom);
return oBottom;
}

public void Clear()
{
list.Clear();
}
{
get
{
if (list.IsEmpty)
throw new InvalidOperationException("stack is empty");

return list.FirstValue;
}
}
public T Tail
{
get
{
if (list.IsEmpty)
throw new InvalidOperationException("stack is empty");

return list.LastValue;
}
}
#endregion

#region ICollection Members
public void CopyTo(Array array, int index)
{
throw new Exception("The method or operation is not implemented.");
}

public int Count
{
get { return list.Count; }
}

public bool IsSynchronized
{
get { throw new Exception("The method or operation is not implemented."); }
}

public object SyncRoot
{
get { throw new Exception("The method or operation is not implemented."); }
}
#endregion

#region IEnumerable Members
public IEnumerator GetEnumerator()
{
return new SLLEnumerator<T>(list);
}
#endregion
}

### Ordered Lists

Recall that we have two foundational data structures -  the array and the linked list. We have also illustrated so far three containers - the stack, the queue and the deque. One of the most versatile containers is the list. A list is a series of items which can be individually accessed by index. In general, there are two kinds of lists - the sorted list and the ordered list. In a sorted list, the sequence in which items occur is important. For example, a book index is a sequence of keywords that are arranged alphabetically, in other words, a sorted list. In an ordered list, the sequence in which items occur is not important. For example, the types of  containers presented in this chapter are not really sorted by anything.

The following shows how to implement an ordered list using a linked list as the underlying foundational data structure. Furthermore, the operations of the ordered list are described by the IList<T> generic interface:

public interface IList<T>
{
T    this[int index] { get; set; }
int  IndexOf(T item);
void Insert(int index, T item);
void RemoveAt(int index);
}

In the following ordered list implementation, a recurring theme is accessing or locating an element at a given index. The main approach is start at the head of the linked list and then loop x number of times until the item is located. Appropriate checks must be added to ensure that index is within limits. For example, the following code shows how to locate the ith element in a linked list:

// An indexer to access the element at index n
public T this[int n]
{
get
{
// Check that given index is within range

if ((n < 0) || (n > sll.Count))
throw new IndexOutOfRangeException("index " + index + " is out of range");

// Now loop over the linked list to retrieve element at the given index. Start at the head of the linked list
// and loop until the given index is reached. Check in each iteration that the element is valid (i.e., not null)

for (int i = 0; i < index && element != null; i++)
element = element.NextElement;

// Return element at index n
return element.Value;
}

The  following shows how to implement a list using a linked list:

class OrderedListAsLinkedList<T> : IList<T> where T : IEquatable<T>
{
// The linked list is used as the underlyind data structure used to hold data

{
}

#region Helpers
Element<T> GetElementAtIndex(int index)
{
// Check that given index is within range
if ((index < 0) || (index > sll.Count))
throw new IndexOutOfRangeException("index " + index + " is out of range");

// Now locate the ith element and insert a new element immediately after the locate element
for (int i = 0; i < index && element != null; i++)
element = element.NextElement;

// Element at this index is guaranteed to be found since index is within range.
// Now just return element
return element;
}
#endregion

#region IList<T> Members
public int IndexOf(T item)
{
int nIndex = 0;
for (Element<T> element = sll.Head; element != null; element = element.NextElement)
{
if (element.Value.Equals(item)) return nIndex;
nIndex++;
}

// If we have reached end of loop then item has not been found
return -1;
}

public void Insert(int index, T item)
{
// Retrieve element at given index
Element<T> element = GetElementAtIndex(index);

// Insertion position located. Insert new element
element.NextElement = new Element<T>(sll, item, element.NextElement);
}

public void RemoveAt(int index)
{
// Now locate the element just before the element to be deleted
Element<T> element = GetElementAtIndex(index);
sll.Delete(element.Value);
}

public T this[int index]
{
get
{
// Retrieve element at given index
Element<T> element = GetElementAtIndex(index);
return element.Value;
}
set
{
Insert(index, value);
}
}
#endregion

#region ICollection<T> Members
{
sll.Append(item);
}

public void Clear()
{
sll.Clear();
}

public bool Contains(T item)
{
return (IndexOf(item) != -1);
}

public void CopyTo(T[] array, int nStartCopyIndex)
{
int nCount = sll.Count;
for (int i = 0; i < nCount; i++)
{
if (i >= nStartCopyIndex)
{
array[i - nStartCopyIndex] = eCurrent.Value;
eCurrent = eCurrent.NextElement;
}
}
}

public int Count
{
get { return sll.Count; }
}

{
get { return false; }
}

public bool Remove(T item)
{
bool bStatus = false;
if (Contains(item))
{
sll.Delete(item);
bStatus = true;
}
return bStatus;
}
#endregion

#region IEnumerable<T> Members
public IEnumerator<T> GetEnumerator()
{
return (IEnumerator<T>)new SLLEnumerator<T>(sll);
}
#endregion

#region IEnumerable Members
System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator()
{
return new SLLEnumerator<T>(sll);
}
#endregion
}

{

// Add, remove and check results
bool bContains;
int n1 = list.IndexOf( 30 );     // 2
int n2 = list.IndexOf( 100 );    // -1
list.RemoveAt( n1 );
int nIndex = list.IndexOf( 30 ); // -1
bContains = list.Contains( 30 );

// Copy elements
int[] arr = new int[list.Count];
list.CopyTo( arr, 0 );
}

### Sorted Lists

A sorted list is similar to an ordered list - they both hold items in sequence. However, in a sorted list, the position of an item is not arbitrary - the items in the sequence appear in a specific order regardless of how items were added. For example, items may appear ordered from smallest to largest.

When inserting an item into a sorted list, we has as a precondition that the list is already sorted. Once an item is inserted, we have the postcondition that the list is still sorted. Therefore, all the items initially in the list that are larger than the item to be inserted need to be moved to the right by one position. The following figure illustrates: The algorithm used to insert an item in a sorted list (based on a linked list) is as follows: The existing sorted linked list is traversed to locate the linked list element which is greater than or equal to the object that is to be inserted. The traversal is done using two variables elementPrevious and elementCurrent. In the event that an item to be inserted is smaller than the first item in the list, the Prepend method is used.

A sorted list implementation is exactly the same as that of the ordered list. The only difference is in the Insert method which is given below ( in other words, replace ordered list implementation of Insert with the method below and you get a sorted list - you will also need to remove IList interface/implementation):

public void Insert(T item)
{
Element<T> elementCurrent = null;
Element<T> elementPrevious = null;

for (elementCurrent = sll.Head; elementCurrent != null; elementCurrent = elementCurrent.NextElement)
{
if (item > elementCurrent.Value)
break;
elementPrevious = elementCurrent;
}

if (elementPrevious == null)
sll.Prepend(item);
else
elementPrevious.InsertAfter(item);
}