 |
General Programming »
Algorithms & Recipes »
Data Structures
Beginner
Data Structures : Part 1 - Singly Linked ListsBy agoatAn easy implementation of a singly linked list |
C#, Windows, .NET, Visual-Studio, Dev
|
|
Advanced Search Add to IE Search |
|
|
|
||||||||||||||||
This is the first in (hopefully) a several part series on data structures. In each part we'll introduce a data structure, discuss the basic idea, the pros, the cons, and the pitfalls.
A Singly Linked List is one of the first complex structures taught. There are gajillion implementations of it in pretty much every language (with the concept of pointers) known to man. The concept is very simply. The list is made up of nodes. Each node tracks one piece of data. It also keeps a reference to the next node (if there is one). You can traverse down the list one way, but not the other because we don't have a pointer to a previous node (that would be a Doubly Linked List - Coming Soon).
using System;
namespace System.Collections.Implementations
{
public class SinglyLinkedList
{
#region Private Variables
// Our next item in the list
private SinglyLinkedList _Next = null;
// The value of the current item
private object _Item = null;
#endregion
}
}
So, in case you couldn't guess, _Next is the next node and _Item
is the value of this node. Wow. So let's add a couple constructors.
#region Constructors
/// <summary>
/// Creates a new SinglyLinkedList object
/// </summary>
public SinglyLinkedList()
{
// Nothing is done here. This is just included so
// people can create new linked lists.
}
/// <summary>
/// Creates a new SinglyLinkedList node for the Item
/// </summary>
///
protected SinglyLinkedList(object Item)
{
// Wow. Not much here either. Just setting the item
_Item = Item;
}
#endregion
You'll find that I like to use a lot of #region tags. I find it keeps code
cleaner. So we've got our basic SinglyLinkedList constructor which doesn't really
do anything. This is used when creating a new SinglyLinkedList object.
The other constructor is used by the class itself and can not be used by users (that's why it's private). It creates a new node within a list. Remember our ground rules for the implementation up above? One of our tenets was that this be a black box to users. They are not allowed to see these internal nodes. Thus, the constructor is private.
Now we need to actually be able to add data to the list.
/// <summary>
/// Gets the last item in the list
/// </summary>
protected SinglyLinkedList Last
{
get
{
SinglyLinkedList Target;
for (Target = this; Target._Next != null; Target = Target._Next) { }
return Target;
}
}
/// <summary>
/// Adds an item to the end of the list
/// </summary>
/// Item to be added
/// <returns>The new length of the list</returns>
public void Add(object Item)
{
Last._Next = new SinglyLinkedList(Item);
}
/// <summary>
/// Combines two linked lists together
/// </summary>
/// Other linked list
public void Append(SinglyLinkedList OtherList)
{
// Glue. Plain and simple glue.
Last._Next = OtherList._Next;
}
I threw two routines for adding items in here along with a property which supports both -
Last. The property is pretty simple. It just loops through the nodes until it
finds the last one.
With that in place, adding a new item is child's play. We just find the last node using
Last and set its' next item to be a new node in our list in Add.
The Append routine looks simple, but it has a little trick in it. We've want to
stick two linked lists together. It'd be easy enough to list all the items in the second list
and add them one by one (or it will be once we add routines to get items), but that would take a
long time for a long list. That is what's called an O(n²) ("Order of n squared")
operation. If it takes t time to add one item, it'll take t * m * n
time to copy a second list over where m and n are the number of items
in the linked lists.
Instead what we do is just take our last item and set it's next pointer to be the second list's
first item with data. Done. This operation is O(n) ("Order of n") meaning that
it takes the same amount of time no matter how many items are in the second list. The time only
depends on the number of items in the first list (which is much nicer). There are ways to get this
down to O(1) ("Order of 1") meaning it takes the same time no matter how many items
there are, but it means tracking some extra stuff and except in rare cases, it's not really worth
it.
/// <summary>
/// Finds a node given the index
/// </summary>
/// Index of the node to find
/// <returns>Node found</returns>
private SinglyLinkedList FindNode(int Index)
{
if (Index < 0)
throw new ArgumentOutOfRangeException("Index", Index,
"Index must be greater than or equal to 0");
SinglyLinkedList Target;
for (Target = this; Index > 0; Index--)
if (Target._Next != null)
Target = Target._Next;
else
throw new ArgumentOutOfRangeException("Index", Index,
"Index greater than the number of items");
return Target;
}
/// <summary>
/// Inserts an item at the specified index in the list
/// </summary>
/// The item to add
/// The index to add the item at
public void Insert(object Item, int Index)
{
// Nothing too tricky here.
SinglyLinkedList PreviousNode = FindNode(Index);
SinglyLinkedList NextItem = new SinglyLinkedList(Item);
NextItem._Next = PreviousNode._Next;
PreviousNode._Next = NextItem;
}
/// <summary>
/// Removes the item at the specified index
/// </summary>
/// Index of the item to remove
public void Remove(int Index)
{
// Nothing too tricky here.
SinglyLinkedList PreviousNode = FindNode(Index);
if (PreviousNode._Next == null)
throw new ArgumentOutOfRangeException("Index", Index,
"Index greater than the number of items");
else
PreviousNode._Next = PreviousNode._Next._Next;
}
The Insert and Remove routines are decidedly more complex. Both
rely on FindNode to find the node they are working on. That routine is very simple.
Just loop through a counter until you get to the right node in the list.
The Insert routine creates a new node for the list. Then it takes the node from
FindNode and sets the new node's next node to be that of the node found. Then it
points the found node's next node to the new node. What we essentially did was wedge a new node
in that list.
The Remove routine does the exact opposite. It finds the node then tells it to
skip over the next node by pointing directly to the next node's next node.
At this point we're done with routines that modify the data and all the ugly routines for reading the data. All we have left are a few accessors...
/// <summary>
/// Gets the Indexth item in the list
/// </summary>
/// Index of the item to get
/// <returns>Item sought</returns>
public object Get(int Index)
{
return FindNode(Index)._Item;
}
/// <summary>
/// Public Accessor for the list items
/// </summary>
public object this[int Index]
{
get
{
return FindNode(Index)._Item;
}
set
{
Insert(value, Index);
}
}
/// <summary>
/// Length of the entire list
/// </summary>
public int Length
{
get
{
int Counter = 0;
for (SinglyLinkedList Target = this; Target._Next != null;
Target = Target._Next)
{
Counter++;
}
return Counter;
}
}
We have to include a Get routine so people can look at the data, but it's super
simple. The this accessor just lets people get or change items based on the index.
This is just a handy convention for people to use, since they have routines for it otherwise. The
Length accessor is a nice to have if people are going to loop through things. We could
add a Replace routine which is simple, but whatever.
These days everyone wants everything handed to them on a platter. So, we're going to add
the IEnumerable and IEnumerator interfaces. Besides, this makes a nice
example of how to use them. First we need to add the interfaces to the class.
public class SinglyLinkedList : IEnumerable, IEnumerator
{
...
}
When you add each one, Visual Studio should be kind enough to create stubs for each routine for you. So lets fill those stubs in:
#region Enumeration Members
/// <summary>
/// Initializes enumeration
/// </summary>
/// <returns>Resets the enumerator and returns itself</returns>
public IEnumerator GetEnumerator()
{
Reset();
return this;
}
/// <summary>
/// This is the currently enumerated item
/// </summary>
private SinglyLinkedList _EnumerationTarget = null;
/// <summary>
/// Resets enumeration to point to the first element
/// </summary>
public void Reset()
{
_EnumerationTarget = this;
}
/// <summary>
/// Gets the currently enumerated object
/// </summary>
public object Current
{
get
{
return _EnumerationTarget._Item;
}
}
/// <summary>
/// Advances to the next object
/// </summary>
/// <returns>Flag determining whether there are no further objects</returns>
public bool MoveNext()
{
_EnumerationTarget = _EnumerationTarget._Next;
return _EnumerationTarget != null;
}
#endregion
There's a whole bunch of stuff here, so lets take a step back. When you actually use something like this...
foreach (object Item in List)
{
...
}
...this actually gets compiled to look something like...
IEnumerator foo = List.GetEnumerator();
foo.Reset();
foo.MoveNext();
for (object Item = foo.Current(); foo.MoveNext() != null; Item = foo.Current())
{
...
}
So, we've got 4 routines there. GetEnumerator is required by the
IEnumerable class. It allows you to return an object which can enumerate through
your class. However, I believe in minimalism, so I'm reusing my SinglyLinkedList
class as the enumerator. So this routine just resets the state of the enumerator and returns
its own class.
Reset is a simple routine, just used to move to the beginning of the list.
Nothing big. So we use an internal variable to point to the root of our linked list.
Current gets the value of the object at the current location in the list.
MoveNext moves the pointer to the next item and returns a boolean detailing whether
we're at the end of the list.
That's all there is to it.
The biggest pro to a Singly Linked List is the simplicity. I wrote this whole article including testing the code in a couple of hours. If you just need to keep track of a smallish list of things, this is the way to go. You can also extend this code very simply to create structures like stacks and queues...
public class Stack : SinglyLinkedList
{
public void Push(object Item)
{
Add(Item);
}
public object Pop()
{
if (_Next == null)
throw new Exception("Stack is Empty");
object Item = Last;
Remove(Length - 1);
return Item;
}
public object Peek()
{
if (_Next == null)
throw new Exception("Stack is Empty");
return Last._Item;
}
}
public class Queue : SinglyLinkedList
{
public void Enqueue(object Item)
{
Add(Item);
}
public object Dequeue()
{
if (_Next == null)
throw new Exception("Queue is Empty");
object Item = this[0];
Remove(0);
return Item;
}
public object Peek()
{
if (_Next == null)
throw new Exception("Queue is Empty");
return this[0];
}
}
The cons are pretty straightforward. You can't do anything really tricky with this data. You can sort but it's a huge pain to do it with simple sorts. Ridiculously complex with fast sorting algorithms. It's also a pretty slow structure. Most operations require iterating through all nodes which is fine when you have a dozen or so items, but pretty sucky when you get a long list.
Stay tuned for the next installment - Doubly Linked Lists :-
| You must Sign In to use this message board. | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||
General 
News 
Question 
Answer 
Joke 
Rant 
Admin
Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads.
|
PermaLink |
Privacy |
Terms of Use
Last Updated: 3 Mar 2004 Editor: Nishant Sivakumar |
Copyright 2004 by agoat Everything else Copyright © CodeProject, 1999-2010 Web22 | Advertise on the Code Project |
I am still using VC6 to develop software but we are looking to make the jump to C# in the near future. Did the Microsoft team port the STL libraries over to C#? If so why would you not wish to use the list container to implement your linked list?
