LinkedList – example

LinkedList

When we need to put some collections into stack(LIFO) or queue(FIFO). The soulition is simple, we create class Stack if we need a “last in first out” strategy and we got some method like insert object to the top of the stack(PUSH), return last element(POP or PEEK). Similary in Queue function(Enqueue) adds object on the end of the queue, return the object which is first. We get it by use Dequeue or Peek depending on whether we want to remove it or not.

It’s clear but what if we have situations where we want to treat collections as a queue, but we have tasks of different priority.And those with higher priority we want to put on the top of the queue.

Here comes help LinkedList which got properties like First,Last and Count of elements. It also has methods like : AddAfter, AddBefore, AddFirst, AddLast, Find and so on.

Example

Let’s see how it look on example.This example has tasks with different priority which we define at the end of the string task in the form of value : 1-hight priority, 0-low priority.

“CleanUp|P=0” – low priority.

“GoToTraning|P=1” – high priority.

The class will have the following items:

public LinkedList<string> List { get; set; } = new LinkedList<string>();
private LinkedListNode<string> _firstElementOnListWithLowPriority;
private string _firstElementWithLowPriority = "";

First is our LinkedList. Second variable is for store the information about first element on linked list with low priority, we will need it to recognize where we should place our tasks with a higher priority. In the third line we have name of our first element needed to find our first element on list.

Method for placing elements in our list:

public void SaveElementToLinkedList(string command)
{
    if (command.Substring(command.Length - 1, 1) == "1")
    {
        if (List.Count == 0) _firstElementOnListWithLowPriority = null;
        if (_firstElementOnListWithLowPriority != null)
        {
            List.AddBefore(_firstElementOnListWithLowPriority, command);
        }
        else
        {
            List.AddFirst(command);
        }
    }
    else
    {
        List.AddLast(command);
        foreach (var item in List)
        {
            if (item.Substring(item.Length - 1, 1) == "0")
            {
                _firstElementWithLowPriority = item; break;
            };
        }
        _firstElementOnListWithLowPriority = List.Find(_firstElementWithLowPriority);
    }
}

The scheme of action is simple. Elements with high priority is put on the top with lower put on the end.Also we are checking if we already have a high priority task in our list if so, we put it before the first task with the low priority.

Tests:

public class AddingElementsToLinkedListTest
{
    private readonly AddingElementsToLinkedList _listOfElementsWithPriority = new AddingElementsToLinkedList();
    public AddingElementsToLinkedListTest()
    {
        _listOfElementsWithPriority.SaveElementToLinkedList("CleanUp|P=0");
        _listOfElementsWithPriority.SaveElementToLinkedList("WashTheCar|P=0");
        _listOfElementsWithPriority.SaveElementToLinkedList("GoToTraning|P=1");
        _listOfElementsWithPriority.SaveElementToLinkedList("WashTheWindow|P=0");
        _listOfElementsWithPriority.SaveElementToLinkedList("EatDinner|P=1");
    }
    [Fact]
    public void FirstElementShouldBeGoToTraning()
    {
        var result = _listOfElementsWithPriority.List.First.Value;

        Assert.Equal(result, "GoToTraning|P=1");
    }
    [Fact]
    public void LastElementShouldBeWashTheWindow()
    {
        var result = _listOfElementsWithPriority.List.Last.Value;

        Assert.Equal(result, "WashTheWindow|P=0");
    }
}

linked list tests

Summary

As we see, to this example – linked list will work very well. Of course we can use it in our own way.

The sky is the limit.

Link to the whole project : HERE

 

One Comment on “LinkedList – example”

  1. Read again first paragraph the link that you sent and compare again. This is my priority list.Implemenation not need be the same implemented as other wikipedia example. It is important that it works on my principles. 😉

Leave a Reply

Your email address will not be published. Required fields are marked *