Home

Operations on Linked Lists
   

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:

Linked List

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:

First Item

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:
    1. Get a reference to the first item
    2. Get the next item to the first and assign it to the next item of the argument
    3. 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:

  1. Get a reference to the item passed as argument
  2. Get the item located at the specified index
  3. Get the item next to the one at the index and assign it to the item next to the argument
  4. Assign the argument to the item next to the one at the index
  5. 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 . . .
 
Home Copyright © 2010-2016, FunctionX