C# Source Code: Source Code for a Doubly Linked List Class
[
Home
|
Contents
|
Search
|
Reply
| Previous | Next ]
C# Source Code
Source Code for a Doubly Linked List Class
By:
Andrew Baker
Email (spam proof):
Email the originator of this post
Date:
Tuesday, October 18, 2005
Hits:
2531
Category:
General/Framework
Article:
A linked list is a chain of structs or objects called nodes. Each node has a reference to another node, which is the next item in the list (unless it's the last node in the list). Lists that only point to the next node are defined as "Single Linked Lists" (forward only) and lists that point to both the next and previous nodes are called "Doubly Linked Lists" (forward and backwards). Below is the source code for a generic Doubly Linked list and example usuage code. using System; #region Public LinkedListNode Class /// <summary> /// A node used to store items in the <c>LinkedList</c> class. /// </summary> public class LinkedListNode { #region Member Variables private LinkedListNode _previousNode; private LinkedListNode _nextNode; private object _value; #endregion Member Variables #region Constructors /// <summary> /// Default constructor /// </summary> /// <param name="previousNode">The previous node.</param> /// <param name="nextNode">The next node.</param> /// <param name="value">The node value.</param> public LinkedListNode(LinkedListNode previousNode, LinkedListNode nextNode, object value) { _previousNode = previousNode; _nextNode = nextNode; _value = value; } #endregion Constructors #region Public Properties /// <summary> /// Gets or sets the value for this node. /// </summary> public object Value { get { return _value; } set { _value = value; } } /// <summary> /// Gets or sets the previous node. /// </summary> public LinkedListNode Previous { get { return _previousNode; } set { _previousNode = value; } } /// <summary> /// Gets or sets the next node. /// </summary> public LinkedListNode Next { get { return _nextNode; } set { _nextNode = value; } } #endregion } #endregion Public LinkedListNode Class #region Public LinkedList Class /// <summary> /// Linked list collection class. /// </summary> public class LinkedList { #region Member Variables private int _count = 0; private int _currentIndex = -1; private LinkedListNode _currentNode = null; private LinkedListNode _head = null; private LinkedListNode _tail = null; #endregion Member Variables #region Public Properties /// <summary> /// Returns the node count. /// </summary> public int Count { get { return _count; } } /// <summary> /// Returns a linked list node. /// </summary> /// <param name="index">The index of the node to return</param> /// <returns>Returns the specified linked list node.</returns> public LinkedListNode Node(int index ) { if ( index == _currentIndex ) { return this.CurrentNode; } else { LinkedListNode node = _head; for ( int i = 0; i < index; i++ ) { node = node.Next; } return node; } } /// <summary> /// Gets or sets the current node. /// </summary> public LinkedListNode CurrentNode { get { return _currentNode; } } /// <summary> /// Returns the index of the current node. /// </summary> public int CurrentNodeIndex { get { return _currentIndex; } } /// <summary> /// Returns the first node in the list. /// </summary> public LinkedListNode Head { get { return _head; } } /// <summary> /// Returns the last node in the list. /// </summary> public LinkedListNode Tail { get { return _tail; } } #endregion #region Public Methods /// <summary> /// Clears the linked list. /// </summary> public void Clear() { _currentNode = null; _tail = null; _head = null; _count = 0; _currentIndex = -1; } /// <summary> /// Moves to the <c>CurrentNode</c> to the first node in the list. /// </summary> public void MoveFirst() { if ( _count > 0 ) { this.SetCurrentNode ( _head ); _currentIndex = 0; } } /// <summary> /// Moves to the <c>CurrentNode</c> to the first node in the list. /// </summary> public void MoveLast() { if ( _count > 0 ) { this.SetCurrentNode ( _tail ); _currentIndex = _count - 1; } } /// <summary> /// Finds the specified node item. /// </summary> /// <param name="item">The node item to find.</param> /// <returns>Returns the index of the node item, or -1 if the item was not found.</returns> public int FindNode( object item ) { LinkedListNode node = _head; for ( int i = 0; i < _count; i++ ) { if ( node.Value == null && item == null ) { // item and node value are both null return i; } else if ( (node.Value != null && node.Value.Equals( item )) || Object.ReferenceEquals( node, item ) ) { // Found the node return i; } node = node.Next; } // Did not find node. return -1; } /// <summary> /// Checks to see if the specified item exists in the list. /// </summary> /// <param name="item">The node item to find.</param> /// <returns>Returns true if the item was found else false.</returns> public bool Contains( object item ) { return this.FindNode( item ) > -1; } /// <summary> /// Removes the specified node from the list. /// </summary> /// <param name="index">The index of the item to remove.</param> public void Remove(int index) { // Get the node to remove LinkedListNode node = this.Node(index); if ( Object.ReferenceEquals( node, _head ) ) { // Removing the head node _head = node.Next; } if ( Object.ReferenceEquals( node, _tail) ) { // Removing the tail node _tail = _tail.Previous; } if ( Object.ReferenceEquals( node, this.CurrentNode ) ) { // Removing the current node _currentNode = _currentNode.Next; _currentIndex++; // Check if this was the last item in the list if ( _currentNode == null ) { // Move back to the head _currentNode = _head; _currentIndex = 0; } } // Now cut the links to this node we are deleting. // Release the reference to this node from the previous node if ( node.Previous != null ) { if ( node.Next != null ) { node.Previous.Next = node.Next.Next; } else { node.Previous.Next = null; } } // Release the reference to this node from the next node if ( node.Next != null ) { if ( node.Previous != null ) { node.Next.Previous = node.Previous.Previous; } else { node.Next.Previous = null; } } // Decrease the count _count--; } /// <summary> /// Adds a node to the linked list, after the <c>CurrentNode</c>. /// </summary> /// <param name="item">The node item to add.</param> public void Add(object item) { if ( _currentNode == null ) { // Start of list _currentNode = new LinkedListNode(null, null, item); _head = _currentNode; _tail = _currentNode; } else { if(_currentNode.Next == null) { // Add item to end of list _currentNode.Next = new LinkedListNode(_currentNode, null, item); _tail = _currentNode.Next; } else { // Insert item _currentNode.Next = new LinkedListNode(_currentNode, _currentNode.Next, item); } _currentNode = _currentNode.Next; } _count++; _currentIndex++; } /// <summary> /// Returns true if there is a next item in the list. /// </summary> public bool HasNext { get { if ( _currentNode == null ) { return false; } return _currentNode == _currentNode.Next != null; } } /// <summary> /// Moves to the specified node. /// </summary> public void MoveTo(int index) { _currentNode = this.Node( index ); _currentIndex = index; } /// <summary> /// Moves to the next Node. /// </summary> public void MoveNext() { if( !HasNext ) { throw new InvalidOperationException("There is no next node to move to."); } else { _currentNode = _currentNode.Next; _currentIndex++; } } /// <summary> /// Returns true if there is a previous item in the list. /// </summary> public bool HasPrevious { get { if ( _currentNode == null ) { return false; } return _currentNode.Previous != null; } } /// <summary> /// Moves to the previous Node. /// </summary> public void MovePrevious() { if( !HasPrevious ) { throw new InvalidOperationException("There is no previous node to move to"); } else { _currentNode = _currentNode.Previous; _currentIndex--; } } /// <summary> /// Gets or sets the specified value for an item in this list. /// </summary> /// <param name="index">The index of the item.</param> public object this[int index] { get { // Return a node value return this.Node( index ).Value; } set { // Update a node value this.Node( index ).Value = value; } } #endregion Public Methods #region Protected Methods /// <summary> /// Sets the current node. /// </summary> /// <param name="node">The node to set as the current node.</param> protected void SetCurrentNode( LinkedListNode node ) { _currentNode = node; } #endregion Protected Methods } #endregion Public LinkedList Class #region DemoCode /// <summary> /// Demonstration class /// </summary> class LinkedListTestClass { /// <summary> /// The main entry point for the application. /// </summary> [STAThread] static void Main(string[] args) { Console.WriteLine("Adding items"); // Populate list LinkedList linkedList = new LinkedList(); linkedList.Add("Andrew"); for ( int i = 0; i < 10; i++) { linkedList.Add(i); } Console.WriteLine( "First Item: " + linkedList[0] ); Console.WriteLine( "Last Item: " + linkedList[linkedList.Count - 1] ); Console.WriteLine( "Count: " + linkedList.Count ); Console.WriteLine( "Contains 9: " + linkedList.Contains( 9 ) ); Console.WriteLine( "Contains 10: " + linkedList.Contains( 10 ) ); Console.WriteLine( "Contains Andrew: " + linkedList.Contains( "Andrew" ) ); // Remove an item then loop over list Console.WriteLine("Looping over items"); linkedList.MoveFirst(); // Remove item 5 Console.WriteLine( "Removing Item 5" ); linkedList.Remove( 5 ); Console.WriteLine( "Count: " + linkedList.Count ); for ( int i = 0; i < linkedList.Count; i++ ) { Console.WriteLine( "Item: " + i + " = " + linkedList.CurrentNode.Value ); if ( linkedList.HasNext ) { linkedList.MoveNext(); } } Console.Read(); } } #endregion DemoCode
Terms and Conditions
Support this site
Download a trial version of the best FTP application on the internet
