Common Routines of a Linked List
|
|
Introduction
|
|
|
To enhance the functionality of a linked list, you will
need to keep track of what item is the first and which one is the last. This
is because some operations must be performed in the starting point of a
collection and some others will need to reference the last item. To keep
track of these two special nodes, you should (must) create a variable for
each:
|
public class Node<T>
{
public T Value { get; set; }
public Node<T> Next { get; set; }
}
public class LinkedList<T>
{
private Node<T> begin;
private Node<T> end;
}
Of course, when the collection starts, the first and the
last items have no value. Therefore, you should initialize them to null or
their default value if you are using a primitive type. Here is an example:
public class Node<T>
{
public T Value { get; set; }
public Node<T> Next { get; set; }
}
public class LinkedList<T>
{
private Node<T> begin;
private Node<T> end;
public LinkedList()
{
begin = null;
end = null;
}
}
Other than that, in previous lessons, we saw that you
should usually (if not always) provide a way to get the current number of
items in a collection. We also saw that you provide a mechanism to get to an
item inside the collection. You can use a method or a read-only indexed
property for the same purpose. You should also provide a Boolean read-only
property that checks whether the list is currently empty or not. Here is an
example:
public class Node<T>
{
public T Value { get; set; }
public Node<T> Next { get; set; }
}
public class LinkedList<T>
{
private Node<T> begin;
private Node<T> end;
private int size;
public LinkedList()
{
begin = null;
end = null;
size = 0;
}
public int Count
{
get { return size; }
}
public bool IsEmpty
{
get
{
if (size == 0)
return true;
return false;
}
}
public Node<T> this[int index]
{
get
{
Node<T> current = begin;
for (int i = size - 1; (i > index) && (current != null); i--)
current = current.Next;
return current;
}
}
public override string ToString()
{
string result = "- ";
Node<T> current = end;
if (end == null)
{
return "The list is currently empty";
// throw new NullReferenceException("The list is currently empty");
}
else
{
for (int i = 0; i < size; i++)
{
result = result + current.Value + " - ";
current = current.Next;
}
}
return result;
}
}
|
Adding a First Item
|
The first item of a collection is the last item that was
added to the list:
Still, if you want, you can create a new item and add it
as the first in the collection. To do this, create a method that receives
the intended item as argument:
- If the list is currently empty, assign the argument to both the first and the last item
- If the list already contains at least one item:
- Get a reference to the first item
- Get the next item to the first and assign it to the next item of the argument
- Replace the next item of the first with the argument
- Increase the number of items in the collection
Here is an example:
using System;
public class Node<T>
{
public T Value { get; set; }
public Node<T> Next { get; set; }
}
public class LinkedList<T>
{
private Node<T> begin;
private Node<T> end;
private int size;
public LinkedList()
{
begin = null;
end = null;
size = 0;
}
public int Count
{
get { return size; }
}
public bool IsEmpty
{
get
{
if (size == 0)
return true;
return false;
}
}
public void AddFirst(Node<T> item)
{
// Get a reference to the node we want to add
Node<T> current = item;
// If the list is currently empty, specify that the first
// and the last are the same and they will receive the argument
if (begin == null)
begin = end = current;
else // If there is already at least one item in the collection
{
// Get a reference to the current first item
Node<T> first = this[0];
// Get the next item to the first and assign it
// to the next item of the argument
current.Next = first.Next;
// Replace the next item of the first with the argument
first.Next = current;
}
// Increase the count of items
size++;
}
public Node<T> this[int index]
{
get
{
Node<T> current = end;
for (int i = size - 1; (i > index) && (current != null); i--)
current = current.Next;
return current;
}
}
}
public class Exercise
{
static int Main(string[] args)
{
Node<string> name = null;
LinkedList<string> employees = new LinkedList<string>();
name = new Node<string>();
name.Value = "Alan Baxter";
employees.AddFirst(name);
name = new Node<string>();
name.Value = "Joan Bramble";
employees.AddFirst(name);
name = new Node<string>();
name.Value = "Lionel Berg";
employees.AddFirst(name);
name = new Node<string>();
name.Value = "Flora Bruze";
employees.AddFirst(name);
name = new Node<string>();
name.Value = "Christopher Fox";
employees.AddFirst(name);
name = new Node<string>();
name.Value = "Holly Madsen";
employees.AddFirst(name);
for (int i = 0; i < employees.Count; i++)
Console.WriteLine("Name {0}: {1}", i + 1, employees[i].Value);
return 0;
}
}
This would produce:
Name 1: Holly Madsen Name 2: Christopher Fox Name 3: Flora Bruze Name 4: Lionel Berg Name 5: Joan Bramble Name 6: Alan Baxter Press any key to continue . . .
|
Using the First Item
|
If you use an indexed list to identify the members of a
collection, the first item of the list is the one with the index of 0. You
can use that feature to get the first member. Here is an example:
public class Exercise
{
static int Main(string[] args)
{
Node<string> name = null;
LinkedList<string> employees = new LinkedList<string>();
. . .
Console.WriteLine("---------------------------------");
Console.WriteLine("First Item: {0}", employees[0].Value);
return 0;
}
}
This would produce:
Name 1: Holly Madsen Name 2: Christopher Fox Name 3: Flora Bruze Name 4: Paul Bertrand Yamaguchi Name 5: Lionel Berg Name 6: Joan Bramble Name 7: Alan Baxter --------------------------------- First Item: Holly Madsen Press any key to continue . . .
Remember that our collection class has a field that
represents the first item of the list. You can create a method or a
read-only property that simply returns that field. Here is an example:
using System;
public class Node<T>
{
public T Value { get; set; }
public Node<T> Next { get; set; }
public Node<T> Nullify()
{
return default(Node<T>);
}
}
public class LinkedList<T>
{
private Node<T> begin;
private Node<T> end;
private int size;
. . . No Change
public Node First
{
get
{
// If the list has no item, throw an exception
if( begin == null )
throw new NullReferenceException(
"There is no item in the collection");
else
{
// This variable will be used for looping
Node temp = null;
// Get a reference to the first item of the collection
Node current = begin;
// Loop through the collection, from one item to the next.
// This allows you to get to the first item
while (current != null)
{
temp = current;
current = current.Next;
}
// Return that first item
return temp;
}
}
}
}
public class Exercise
{
static int Main(string[] args)
{
Node<string> name = null;
LinkedList<string> employees = new LinkedList<string>();
name = new Node<string>();
name.Value = "Alan Baxter";
employees.AddFirst(name);
name = new Node<string>();
name.Value = "Joan Bramble";
employees.AddFirst(name);
name = new Node<string>();
name.Value = "Lionel Berg";
employees.AddFirst(name);
name = new Node<string>();
name.Value = "Flora Bruze";
employees.AddFirst(name);
name = new Node<string>();
name.Value = "Christopher Fox";
employees.AddFirst(name);
name = new Node<string>();
name.Value = "Holly Madsen";
employees.AddFirst(name);
for (int i = 0; i < employees.Count; i++)
Console.WriteLine("Name {0}: {1}", i + 1, employees[i].Value);
Console.WriteLine("----------------------------------");
Console.WriteLine("First Item: {0}", employees.First.Value); // employees[0].Value);
return 0;
}
}
This would produce:
Name 1: Holly Madsen Name 2: Christopher Fox Name 3: Flora Bruze Name 4: Lionel Berg Name 5: Joan Bramble Name 6: Alan Baxter ---------------------------------- First Item: Holly Madsen Press any key to continue . . .
Another way you can use the first position is to replace
the item in that position with another item.
|
Adding the Last Item
|
The technique we saw in the previous lesson about adding
a new item to a linked list actually adds the item to the end of the list.
This means that we can just name that method AddLast and the result would be
the same. Here is an example:
using System;
public class Node<T>
{
public T Value { get; set; }
public Node<T> Next { get; set; }
}
public class LinkedList<T>
{
. . . No Change
public void AddLast(Node<T> item)
{
// Get a reference to the new item that will be added
// and assign the argument to that reference
Node<T> current = item;
// Indicate that the first node will become next to the new item
current.Next = begin;
// Indicate that the new item becomes the first of the collection
begin = current;
// Increase the count of items
size++;
}
}
|
Using the Last Item
|
In some cases, you may want to get the last item of a
collection. Here is an example of how to access it:
using System;
public class Node<T>
{
public T Value { get; set; }
public Node<T> Next { get; set; }
public Node<T> Nullify()
{
return default(Node<T>);
}
}
public class LinkedList<T>
{
private Node<T> begin;
private Node<T> end;
private int size;
public LinkedList()
{
begin = null;
end = null;
size = 0;
}
public int Count
{
get { return size; }
}
public Node<T> First
{
get
{
// If the list has no item, throw an exception
if( begin == null )
throw new NullReferenceException(
"There is no item in the collection");
else
{
// This variable will be used for looping
Node<T> temp = null;
// Get a reference to the first item of the collection
Node<T> current = begin;
// Loop through the collection, from one item to the next.
// This allows you to get to the first item
while (current != null)
{
temp = current;
current = current.Next;
}
// Return that first item
return temp;
}
}
}
public Node<T> Last
{
get
{
return begin;
}
}
public void AddLast(Node<T> item)
{
// Get a reference to the new item that will be added
// and assign the argument to that reference
Node<T> current = item;
// Indicate that the first node will become next to the new item
current.Next = begin;
// Indicate that the new item becomes the first of the collection
begin = current;
// Increase the count of items
size++;
}
public Node<T> this[int index]
{
get
{
if( (index == 0) && (begin == null) )
throw new NullReferenceException(
"There is no item in the collection");
else
{
Node<T> current = begin;
for (int i = size - 1; (i > index) && (current != null); i--)
current = current.Next;
return current;
}
}
}
}
public class Exercise
{
static int Main(string[] args)
{
Node<string> name = null;
LinkedList<string> employees = new LinkedList<string>();
name = new Node<string>();
name.Value = "Alan Baxter";
employees.AddLast(name);
name = new Node<string>();
name.Value = "Joan Bramble";
employees.AddLast(name);
name = new Node<string>();
name.Value = "Paul Bertrand Yamaguchi";
employees.AddLast(name);
name = new Node<string>();
name.Value = "Lionel Berg";
employees.AddLast(name);
name = new Node<string>();
name.Value = "Flora Bruze";
employees.AddLast(name);
name = new Node<string>();
name.Value = "Christopher Fox";
employees.AddLast(name);
name = new Node<string>();
name.Value = "Holly Madsen";
employees.AddLast(name);
for (int i = 0; i < employees.Count; i++)
Console.WriteLine("Name {0}: {1}", i + 1, employees[i].Value);
Console.WriteLine("----------------------------------");
Console.WriteLine("First Item: {0}", employees.First.Value);
Console.WriteLine("Last Item: {0}", employees.Last.Value);
Console.WriteLine("----------------------------------");
return 0;
}
}
This would produce:
Name 1: Alan Baxter Name 2: Joan Bramble Name 3: Paul Bertrand Yamaguchi Name 4: Lionel Berg Name 5: Flora Bruze Name 6: Christopher Fox Name 7: Holly Madsen ---------------------------------- First Item: Alan Baxter Last Item: Holly Madsen ---------------------------------- Press any key to continue . . .
. Here is an example:
public
|
Inserting an Item Using an Index
|
As you should know already, inserting an item consists
of putting one between two existing items. One way you can do this consists
of passing the new item and an index. When implementing the method, first
identify the index. If the user passes an index of 0, this is equivalent to
adding the first item. If the user passes an index that is equal to the size
of the list, add the item as the last. If the user passes an index that is
larger than the size of the list, you can either throw an exception or add
the item as the last. If the user passes an index that is positive but less
than the total size of the list:
- Get a reference to the item passed as argument
- Get the item located at the specified index
- Get the item next to the one at the index and assign it to the item next to the argument
- Assign the argument to the item next to the one at the index
- Increase the number of items
Here is an example:
public class Node<T>
{
public T Value { get; set; }
public Node<T> Next { get; set; }
}
public class LinkedList<T>
{
private Node<T> First;
private Node<T> end;
private int size;
. . . No Change
public void Insert(Node<T> item, int index)
{
if (index == 0)
AddFirst(item);
else if (index >= size)
AddLast(item);
else
{
Node<T> current = item;
Node<T> itemAtIndex = this[index];
current.Next = itemAtIndex.Next;
itemAtIndex.Next = current;
size++;
}
}
}
Here is an example of testing the method:
public class Exercise
{
static int Main(string[] args)
{
Node<string> name = null;
LinkedList<string> employees = new LinkedList<string>();
name = new Node<string>();
name.Value = "Mathew Jeremy Williams";
employees.Insert(name, 3);
name = new Node<string>();
name.Value = "Alan Baxter";
employees.AddLast(name);
name = new Node<string>();
name.Value = "Joan Bramble";
employees.AddLast(name);
name = new Node<string>();
name.Value = "Lionel Berg";
employees.AddLast(name);
name = new Node<string>();
name.Value = "Paul Bertrand Yamaguchi";
employees.AddLast(name);
name = new Node<string>();
name.Value = "Flora Bruze";
employees.AddLast(name);
name = new Node<string>();
name.Value = "Christopher Fox";
employees.AddLast(name);
name = new Node<string>();
name.Value = "Holly Madsen";
employees.AddLast(name);
for (int i = 0; i < employees.Count; i++)
Console.WriteLine("Name {0}: {1}", i + 1, employees[i].Value);
return 0;
}
}
This would produce:
Name 1: Mathew Jeremy Williams
Name 2: Alan Baxter
Name 3: Joan Bramble
Name 4: Lionel Berg
Name 5: Paul Bertrand Yamaguchi
Name 6: Flora Bruze
Name 7: Christopher Fox
Name 8: Holly Madsen
Press any key to continue . . .
Here is another test:
public class Exercise
{
static int Main(string[] args)
{
Node<string> name = null;
LinkedList<string> employees = new LinkedList<string>();
name = new Node<string>();
name.Value = "Alan Baxter";
employees.AddLast(name);
name = new Node<string>();
name.Value = "Joan Bramble";
employees.AddLast(name);
name = new Node<string>();
name.Value = "Mathew Jeremy Williams";
employees.Insert(name, 3);
name = new Node<string>();
name.Value = "Lionel Berg";
employees.AddLast(name);
name = new Node<string>();
name.Value = "Paul Bertrand Yamaguchi";
employees.AddLast(name);
name = new Node<string>();
name.Value = "Flora Bruze";
employees.AddLast(name);
name = new Node<string>();
name.Value = "Christopher Fox";
employees.AddLast(name);
name = new Node<string>();
name.Value = "Holly Madsen";
employees.AddLast(name);
for (int i = 0; i < employees.Count; i++)
Console.WriteLine("Name {0}: {1}", i + 1, employees[i].Value);
return 0;
}
}
This would produce:
Name 1: Alan Baxter
Name 2: Joan Bramble
Name 3: Mathew Jeremy Williams
Name 4: Lionel Berg
Name 5: Paul Bertrand Yamaguchi
Name 6: Flora Bruze
Name 7: Christopher Fox
Name 8: Holly Madsen
Press any key to continue . . .
Here is one more test:
public class Exercise
{
static int Main(string[] args)
{
Node<string> name = null;
LinkedList<string> employees = new LinkedList<string>();
name = new Node<string>();
name.Value = "Alan Baxter";
employees.AddLast(name);
name = new Node<string>();
name.Value = "Joan Bramble";
employees.AddLast(name);
name = new Node<string>();
name.Value = "Lionel Berg";
employees.AddLast(name);
name = new Node<string>();
name.Value = "Paul Bertrand Yamaguchi";
employees.AddLast(name);
name = new Node<string>();
name.Value = "Flora Bruze";
employees.AddLast(name);
name = new Node<string>();
name.Value = "Christopher Fox";
employees.AddLast(name);
name = new Node<string>();
name.Value = "Mathew Jeremy Williams";
employees.Insert(name, 3);
name = new Node<string>();
name.Value = "Holly Madsen";
employees.AddLast(name);
for (int i = 0; i < employees.Count; i++)
Console.WriteLine("Name {0}: {1}", i + 1, employees[i].Value);
return 0;
}
}
This would produce:
Name 1: Alan Baxter
Name 2: Joan Bramble
Name 3: Lionel Berg
Name 4: Mathew Jeremy Williams
Name 5: Paul Bertrand Yamaguchi
Name 6: Flora Bruze
Name 7: Christopher Fox
Name 8: Holly Madsen
Press any key to continue . . .
|
Deleting an Item
|
|
Deleting the First Item
|
To delete the first item of a linked list, get a
reference to the next item of the starting positio, assign that reference to
the next item to the first. Here is an example:
public void DeleteFirst()
{
if (begin == null)
return;
Node<T> current = begin.Next;
begin.Next = current;
size--;
}
|
Deleting the Last Item
|
This would produce:
Number of Items: 0 Press any key to continue . . .
No comments :
Post a Comment