TECHY360
Everything You Need To Know About Tech

Linked list: Algorithms and data structures for beginners

0 16

The first data structure we consider is a linked list. There are two reasons for this: the first is that the linked list is used almost everywhere – from the OS to the games, and the second is that many other data structures are built on its basis.

Linked list

The main purpose of the linked list is to provide a mechanism for storing and accessing an arbitrary amount of data. As the name suggests, this is achieved by linking data together into a list.

Before we move on to a coherent list, let’s remember how the data is stored in an array.

As shown in the figure, the data in the array is stored in a continuous section of memory divided into cells of a certain size. Access to data in cells is carried out by reference to their location – the index.

This is a great way to store data. Most programming languages ​​allow one way or another to allocate memory as an array and manipulate its contents. Sequential data storage improves performance (data locality), makes it easy to iterate through the content and access an arbitrary item by index.

However, sometimes an array is not the most appropriate structure.

Suppose that our program has the following requirements:

  • Read a certain number of integers from the source (method NextValue) until a number is found 0xFFFF.
  • Pass the read numbers to the method ProcessItems

Since the requirements state that the read numbers are transferred to the method ProcessItemsat one time, the solution will be an array of integers:

void LoadData ()
{
    // Suppose that the elements will be no more than 20
    int [] values ​​= new int [20];
    for (int i = 0; i <values.Length; i ++)
    {
        if (values ​​[i] == 0xFFFF)
        {
            break;
        }

        values ​​[i] = NextValue ();
    }

    ProcessItems (values);
}

void ProcessItems (int [] values)
{
    // ... process the data.
}

This solution has a number of problems, but the most obvious of them is what happens if you need to read more than 20 values? In this implementation, values ​​from 21 onwards are simply ignored. You can allocate more memory – 200 or 2000 items. You can give the user the opportunity to choose the size of the array. Or allocate memory for a larger array when filling the old one and copy the elements. But all these decisions complicate the code and waste memory unnecessarily.

We need a collection that allows you to add an arbitrary number of elements and sort them in the order of addition. The size of the collection should be unlimited, and we do not need random access. We need a coherent list.

Before turning to its implementation, let’s look at how the solution to our problem might look like.


static void LoadItems ()
{
    LinkedList list = new LinkedList ();
    while (true)
    {
        int value = NextValue ();
        if (value! = 0xFFFF)
        {
            list.Add (value);
        }
        else
        {
            break;
        }
    }

    ProcessItems (list);
}

static void ProcessItems (LinkedList list)
{
        // ... process the data.
}

Please note: the problems inherent in the first solution are no longer there — we cannot allocate enough or, on the contrary, too much memory for the array.

In addition, from this code you can see that our list will accept a type parameter <T>and implement the interfaceIEnumerable

Implementing the LinkedList class

Class node

At the heart of the linked list is the concept of a node or element (Node). A node is a container that allows you to store data and receive the next node.

In the simplest case, the class Nodecan be implemented like this:

public class Node
{
    public int Value { get; set; }
    public Node Next { get; set; }
}

Now we can create a primitive linked list. Allocate memory for the three nodes ( firstmiddlelast) and connect them in series:

// +-----+------+
// |  3  | null +
// +-----+------+
Node first = new Node { Value = 3 };

// +-----+------+    +-----+------+
// |  3  | null +    |  5  | null +
// +-----+------+    +-----+------+
Node middle = new Node { Value = 5 };

// +-----+------+    +-----+------+
// |  3  |  *---+--->|  5  | null +
// +-----+------+    +-----+------+
first.Next = middle;

// +-----+------+    +-----+------+   +-----+------+
// |  3  |  *---+--->|  5  | null +   |  7  | null +
// +-----+------+    +-----+------+   +-----+------+
Node last = new Node { Value = 7 };

// +-----+------+    +-----+------+   +-----+------+
// |  3  |  *---+--->|  5  |  *---+-->|  7  | null +
// +-----+------+    +-----+------+   +-----+------+
middle.Next = last;

Now we have a list of three items, from firstand to last. The Nextlast node field has a value null, which indicates that this is the last element. With this list you can already perform various operations. For example, print data from each item:

private static void PrintList(Node node)
{
    while (node != null)
    {
        Console.WriteLine(node.Value);
        node = node.Next;
    }
}

The method is PrintListiterated over the elements of the list: prints the value of the field Valueand moves to the next node by a link in the field Next.

Now that we know what the linked list node should look like, let’s look at an example class implementation LinkedListNode.


public class LinkedListNode
{
    ///
    /// Constructor of a new node with the Value value.
    ///
    public LinkedListNode (T value)
    {
        Value = value;
    }

    ///
    /// Value field.
    ///
    public T Value {get; internal set; }

    ///
    /// Link to the next node in the list (if the node is the last, then null).
    ///
    public LinkedListNode Next {get; internal set; }
}

LinkedList class

Before implementing our coherent list, you need to understand how we will work with it.

Earlier, we saw that the collection should support any data type, which means we need to implement a generic interface.

Since we use the .NET platform, it makes sense to implement our class in such a way that its behavior is similar to the behavior of the built-in collections. The easiest way to do this is to implement an interface ICollection<T>. Notice that we are implementing ICollection<T>, rather than Ilist<T>, because the interface Ilist<T>allows access to the elements by index. Although random access to items as a whole is useful, it cannot be effectively implemented in a linked list.

Considering all the above, let’s outline a rough outline of the class, and then fill in the missing methods.

public class LinkedList :
    System.Collections.Generic.ICollection
{
    public void Add(T item)
    {
        throw new System.NotImplementedException();
    }

    public void Clear()
    {
        throw new System.NotImplementedException();
    }

    public bool Contains(T item)
    {
        throw new System.NotImplementedException();
    }

    public void CopyTo(T[] array, int arrayIndex)
    {
        throw new System.NotImplementedException();
    }

    public int Count
    {
        get;
        private set;
    }

    public bool IsReadOnly
    {
        get { throw new System.NotImplementedException(); }
    }

    public bool Remove(T item)
    {
        throw new System.NotImplementedException();
    }

    public System.Collections.Generic.IEnumerator GetEnumerator()
    {
        throw new System.NotImplementedException();
    }

    System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator()
    {
        throw new System.NotImplementedException();
    }
}

Add method

  • Behavior: Adds an item to the end of the list.
  • Difficulty: O (1)

Adding an item to the linked list is done in three steps:

  1. Create an instance of the class LinkedListNode.
  2. Find the last node in the list.
  3. Set the value of the field of the Nextlast node of the list so that it points to the created node.

The main difficulty is to find the last node in the list. You can do this in two ways. The first is to save the pointer to the first node in the list and iterate over the nodes until we reach the last one. In this case, we do not need to save the pointer to the last node, which allows us to use less memory (depending on the size of the pointer on your platform), but requires a walk through the entire list each time a node is added. This means that the method Addwill take O (n) time.

The second method is to save a pointer to the last node in the list, and then when adding a new node, we change the pointer so that it points to the new node. This method is preferable because it is executed in O (1) time.

The first thing we need to do is add two private fields to the class LinkedList: references to the first (head) and last (tail) nodes.

private LinkedListNode _head;
private LinkedListNode _tail;

Now we can add a method that performs the three necessary steps.

public void Add(T value)
{
    LinkedListNode node = new LinkedListNode(value);

    if (_head == null)
    {
        _head = node;
        _tail = node;
    }
    else
    {
        _tail.Next = node;
        _tail = node;
    }

    Count++;
}

First we create an instance of the class LinkedListNode. Then we check if the list is empty. If the list is empty, we simply set the values ​​of the fields _headand _tailso that they point to the new node. This node in this case will be both the first and the last in the list. If the list is not empty, the node is added to the end of the list, and the field _tailnow points to the new end of the list.

The field is Countincremented when a node is added in order to preserve the interface contract ICollection<T>. The Count field returns the exact number of items in the list.

Remove method

  • Behavior: Removes the first item in the list with a value equal to the one passed. Returns trueif the item has been deleted and falseotherwise.
  • Difficulty: O (n)
Related Posts
1 of 7

Before analyzing the method Remove, let’s see what we want to achieve. The following figure is a list of four items. We remove the element with the value “3”.

After deleting a node, a node field Nextwith a value of “2” will point to a node with a value of “4”.

The basic algorithm for deleting an element is:

  1. Find the node to be deleted.
  2. Change the value of the field of the Nextprevious node so that it points to the node following the one to be deleted.

As always, the main problem lies in the details. Here are some of the cases that need to be addressed:

  • The list may be empty, or the value that we pass to the method may not be present in the list. In this case, the list will remain unchanged.
  • Removable node may be the only one in the list. In this case, we set the field values ​​to _headand _tailequal null.
  • The deleted node will be at the top of the list. In this case, we write the _headlink to the next node.
  • The deleted node will be in the middle of the list.
  • The deleted node will be at the end of the list. In this case, we write the _taillink to the penultimate node, and Nextwrite it in its field null.
public bool Remove(T item)
{
    LinkedListNode previous = null;
    LinkedListNode current = _head;

    // 1: Empty list: do nothing.
    // 2: One element: set Previous = null.
    // 3: Several elements:
    // a: The first element to delete.
    // b: Remove the element in the middle or end.

    while (current! = null)
    {
        if (current.Value.Equals (item))
        {
            // Node in the middle or at the end.
            if (previous! = null)
            {
                // Case 3b.

                // To: Head -> 3 -> 5 -> null
                // After: Head -> 3 ------> null
                previous.Next = current.Next;

                // If at the end, change _tail.
                if (current.Next == null)
                {
                    _tail = previous;
                }
            }
            else
            {
                // Case 2 or 3a.

                // To: Head -> 3 -> 5
                // After: Head ------> 5

                // Head -> 3 -> null
                // Head ------> null
                _head = _head.Next;

                // Is the list empty now?
                if (_head == null)
                {
                    _tail = null;
                }
            }

            Count--;

            return true;
        }

        previous = current;
        current = current.Next;
    }

    return false;
}

The field is Countdecremented when a node is deleted.

Contains method

  • Behavior: Returns trueor falsedepending on whether the item you are looking for is in the list.
  • Difficulty: O (n)

The method is Containsquite simple. It scans every element of the list, from the first to the last, and returns trueas soon as it finds a node whose value is equal to the passed parameter. If such a node is not found, and the method has reached the end of the list, it is returned false.

public bool Contains(T item)
{
    LinkedListNode current = _head;
    while (current != null)
    {
        if (current.Value.Equals(item))
        {
            return true;
        }

        current = current.Next;
    }

    return false;
}

GetEnumerator method

  • Behavior: Returns an instance IEnumeratorthat allows iteration through list items.
  • Difficulty: Getting an iterator – O (1). Pass through all elements – O (n).

The returned iterator iterates through the entire list from the first to the last node and returns the value of each element using a keyword yield.

IEnumerator IEnumerable.GetEnumerator()
{
    LinkedListNode current = _head;
    while (current != null)
    {
        yield return current.Value;
        current = current.Next;
    }
}

IEnumerator IEnumerable.GetEnumerator()
{
    return ((IEnumerable)this).GetEnumerator();
}

Clear method

  • Behavior: Removes all items from the list.
  • Difficulty: O (1)

The method Clearsimply sets the values of fields _headand _tailequal null. Since C # is a language with automatic memory management, there is no need to explicitly delete unused nodes. The client calling the method must ensure that the values ​​of the nodes are correctly deleted, if necessary.

public void Clear()
{
    _head = null;
    _tail = null;
    Count = 0;
}

CopyTo method

  • Behavior: Copies the contents of the list into the specified array, starting at the specified index.
  • Difficulty: O (n)

The method CopyTogoes through the list and copies the elements into an array using assignment. The client calling method must ensure that the array is large enough to accommodate all the elements of the list.

public void CopyTo(T[] array, int arrayIndex)
{
    LinkedListNode current = _head;
    while (current != null)
    {
        array[arrayIndex++] = current.Value;
        current = current.Next;
    }
}

Count method

  • Behavior: Returns the number of items in a list. Returns 0 if the list is empty.
  • Difficulty: O (1)

Count– A field with a public getter and a private setter. Changing its value is carried out in the methods AddRemoveand Clear.

public int Count
{
    get;
    private set;
}

IsReadOnly method

  • Behavior: Returns trueif the list is read only.
  • Difficulty: O (1)
public bool IsReadOnly
{
    get { return false; }
}

Doubly linked list

The linked list that we just created is also called “simply linked.” This means that between nodes there is only one connection in a single direction from the first node to the last. There is also a fairly common version of the list that provides access to both ends – a doubly linked list.

In order to create a doubly linked list, we need to add a LinkedListNodefield to the class Previousthat will contain a link to the previous list item.

Next, we consider only the differences in the implementation of a simply connected and doubly linked list.

Class node

The only change that needs to be made to the class LinkedListNodeis to add a field with a link to the previous node.

public class LinkedListNode
{
    //
    // Constructor of a new node with the Value value.
    //
    //
    public LinkedListNode (T value)
    {
        Value = value;
    }

    //
    // Value field.
    //
    public T Value {get; internal set; }

    //
    // Link to the next node in the list (if the node is the last, then null).
    //
    public LinkedListNode Next {get; internal set; }

    //
    // Link to the previous list node (if the node is first, then null).
    //
    public LinkedListNode Previous {get; internal set; }
}

AddFirst method

While a single-linked list allows you to add elements only to the end, using a doubly-linked list, we can add elements both to the beginning and to the end, using methods AddFirstand, AddLastaccordingly. The method ICollection<T>.Addwill call AddLastfor compatibility with a single-linked list.

  • Behavior: Adds the passed item to the top of the list.
  • Difficulty: O (1)

When adding an element to the top of the list, the sequence of actions is approximately the same as when adding an element to a single linked list.

  1. Set the value of the field Nextin the new node so that it points to the former first node.
  2. Set the field value Previousin the former first node so that it points to the new node.
  3. Update the field _tailif necessary and increment the fieldCount

public void AddFirst (T value)
{
    LinkedListNode node = new LinkedListNode (value);

    // Save the link to the first item.
    LinkedListNode temp = _head;

    // _head points to the new node.
    _head = node;

    // Insert the list behind the first item.
    _head.Next = temp;

    if (Count == 0)
    {
        // If the list was empty, then head and tail should
        // point to the new node.
        _tail = _head;
    }
    else
    {
        // To: head -------> 5 7 -> null
        // After: head -> 3 5 7 -> null
        temp.Previous = _head;
    }

    Count ++;
}

AddLast method

  • Behavior: Adds the passed item to the end of the list.
  • Difficulty: O (1)

Adding a node to the end of the list is easier than adding it to the beginning. We simply create a new node and update the fields _headand _tailthen increment the field Count.

public void AddLast (T value)
{
    LinkedListNode node = new LinkedListNode (value);

    if (Count == 0)
    {
        _head = node;
    }
    else
    {
        _tail.Next = node;

        // To: Head -> 3 5 -> null
        // After: Head -> 3 5 7 -> null
        // 7.Previous = 5
        node.Previous = _tail;
    }

    _tail = node;
    Count ++;
}

As mentioned earlier, ICollection<T>.Addjust calling AddLast.

public void Add(T value)
{
    AddLast(value);
}

RemoveFirst method

Like the method Add, it Removewill be divided into two methods, allowing you to remove items from the beginning and from the end of the list. The method ICollection<T>.Removewill also remove elements from the beginning, but now it will still update the fields Previousin those nodes where it is needed.

  • Behavior: Removes the first item in the list. If the list is empty, do nothing. Returns trueif the item has been deleted and falseotherwise.
  • Difficulty: O (1)

RemoveFirstestablishes a link headto the second node of the list and resets the field of Previousthis node, thus removing all references to the previous first node. If the list was empty or contained only one element, then the fields _headand _tailbecome equal null.


public void RemoveFirst ()
{
    if (Count! = 0)
    {
        // To: Head -> 3 5
        // After: Head -------> 5

        // Head -> 3 -> null
        // Head ------> null
        _head = _head.Next;

        Count--;

        if (Count == 0)
        {
            _tail = null;
        }
        else
        {
            // 5.Previous was 3; now null.
            _head.Previous = null;
        }
    }
}

RemoveLast method

  • Behavior: Removes the last item in the list. If the list is empty, do nothing. Returns trueif the item has been deleted and falseotherwise.
  • Difficulty: O (1)

RemoveLastsets the field value _tailso that it points to the last but one element of the list and thus removes the last element. If the list was empty, or contained only one element, then the fields _headand _tailbecome equal null.

public void RemoveLast ()
{
    if (Count! = 0)
    {
        if (Count == 1)
        {
            _head = null;
            _tail = null;
        }
        else
        {
            // To: Head -> 3 -> 5 -> 7
            // Tail = 7
            // After: Head -> 3 -> 5 -> null
            // Tail = 5
            // Reset 5.Next
            _tail.Previous.Next = null;
            _tail = _tail.Previous;
        }

        Count--;
    }
}

Remove method

  • Behavior: Removes the first item in the list with a value equal to the one passed. Returns trueif the item has been deleted and falseotherwise.
  • Difficulty: O (n)

The method is ICollection<T>.Remove()almost the same as in the single-linked list. The only difference is that now we need to change the field value Previouswhen deleting a node. In order not to repeat the code, this method calls RemoveFirstwhen deleting the first node.

public bool Remove(T item)
{
    LinkedListNode previous = null;
    LinkedListNode current = _head;

   
// 1: Empty list: do nothing.
    // 2: One element: set Previous = null.
    // 3: Several elements:
    // a: The first element to delete.
    // b: Remove the element in the middle or end.

    while (current! = null)
    {
        // Head -> 3 -> 5 -> 7 -> null
        // Head -> 3 ------> 7 -> null
        if (current.Value.Equals (item))
        {
            // Node in the middle or at the end.
            if (previous! = null)
            {
                // Case 3b.
                previous.Next = current.Next;

                // If at the end, change _tail.
                if (current.Next == null)
                {
                    _tail = previous;
                }
                else
                {
                    // To: Head -> 3 5 7 -> null
                    // After: Head -> 3 7 -> null

                    // previous = 3
                    // current = 5
                    // current.Next = 7
                    // So ... 7.Previous = 3
                    current.Next.Previous = previous;
                }

                Count--;
            }
            else
            {
                // Case 2 or 3a.
                RemoveFirst();
            }

            return true;
        }

        previous = current;
        current = current.Next;
    }

    return false;
}

Why do you need a doubly linked list?

So, we can add items to the top of the list and to the end. What does this give us? In the form in which it is implemented now, there are no special advantages over the usual single-linked list. But if we add getters for fields headand tail, the user of our list will be able to implement many different algorithms.

public LinkedListNode Head
{
    get
    {
        return _head;
    }
}

public LinkedListNode Tail
{
    get
    {
        return _tail;
    }
}

So we can iterate through the list manually, including from the last element to the first.

In this example, we use the fields Tailand Previousto get around the list backwards.

public void ProcessListBackwards()
{
    LinkedList list = new LinkedList();
    PopulateList(list);

    LinkedListNode current = list.Tail;
    while (current != null)
    {
        ProcessNode(current);
        current = current.Previous;
    }
}

In addition, a doubly linked list makes it easy to implement a doubly linked queue, which, in turn, is the building block for other data structures. We will return to it later, in the appropriate part.

To be continued

This concludes the analysis of linked lists. Next time we will analyze the structure of vectors in detail (array list).

Get real time updates directly on you device, subscribe now.

Comments
Loading...

This website uses cookies to improve your experience. We'll assume you're ok with this, but you can opt-out if you wish. Accept Read More