This is your first visit inside The Matrix. Welcome!

The Matrix has you…

This place will take you into the mirage of learning C# programming language, without any previous coding experience being required

Follow the White Rabbit…█

Close
Sunday, June 24, 2018 08:50

Linked List

Singly and doubly linked lists (also known simply as Linked Lists) hold collection of elements, which preserve their order. Their representation in the memory is dynamic, pointer-based. They are linked sequences of elements. Adding is a fast operation, but it is a bit slower than adding to a List, because every time when we add an element to a linked list, we allocate a new memory area. The memory allocation works at speeds which cannot be easily predicted. Searching in a linked list is a slow operation because we have to traverse through all of its elements. Accessing an element by its index is a slow operation because there is no indexing in singly and doubly linked lists. You have to go through all the elements from the start, one by one, instead. Removing an element at a specified index is a slow operation because reaching the element through its index is a slow operation. Removing an element with a specified value is a slow operation too, because it involves searching. Linked list can quickly add and remove elements (with a constant complexity) at its two ends (head and tail). Hence, it is very handy for an implementation of Stacks, Queues and similar data structures. Linked lists are rarely used in practice because the dynamic arrays (List) can do almost exact same operations LinkedList can do, plus for the most of them they work faster and are more comfortable. LinkedList often uses more memory than an array or List. This is because of the memory allocation in the .NET Framework, and how objects are allocated. When you need a linked list, use List instead, because it doesn’t work slower and it gives you better speed and flexibility. Use LinkedList when you have to add and remove elements at both ends of the data structure.

// create a new linked list.
LinkedList<string> linked = new LinkedList<string>();

// use AddLast method to add elements at the end.
linked.AddLast("cat");
linked.AddLast("dog");
linked.AddLast("man");
// use AddFirst method to add element at the start.
linked.AddFirst("first");

// insert a node before the second node (after the first node)
LinkedListNode<string> node = linked.Find("one");
linked.AddAfter(node, "inserted");

// loop through the linked list.
foreach (var value in linked)
{
    Console.WriteLine(value);
}

The primary advantage of linked lists over arrays is that the links provide us with the capability to rearrange the items efficiently.

The main methods of a Linked List are the following:

AddFirst(), AddLast(), AddBefore(), AddAfter() – appends or prepends elements to the linked list’s internal data structure, respectively, adds before or after a certain element. Example:

using System;
using System.Collections.Generic;

class Program
{
    static void Main()
    {
        // Create a new linked list object instance.
        LinkedList<string> linked = new LinkedList<string>();

        // Use AddLast method to add elements at the end.
        // Use AddFirst method to add element at the start.
        linked.AddLast("cat");
        linked.AddLast("dog");
        linked.AddLast("man");
        linked.AddFirst("first");

        //add a new element after a certain other element
        LinkedListNode<string> current = linked.FindLast("dog");
        linked.AddAfter(current, "cow");
        //add a new element before a certain other element
        linked.AddBefore(current, "bird");
        
        // Loop through the linked list with the foreach-loop.
        foreach (var item in linked)
            Console.WriteLine(item);
    }
}

Find() – Searches for an element in its internal collection of elements. It returns a reference to an instance of the LinkedListNode class, which contains pointers to the other elements (the results of the search). Example:

using System;
using System.Collections.Generic;

class Program
{
    static void Main()
    {
        // Create a new linked list.
        LinkedList<string> linked = new LinkedList<string>();

        // First add three elements to the linked list.
        linked.AddLast("one");
        linked.AddLast("two");
        linked.AddLast("three");

        // Insert a node containing the results of a search, before the second node (after the first node)
        LinkedListNode<string> node = linked.Find("one");
        linked.AddAfter(node, "inserted");

        // Loop through the linked list.
        foreach (var value in linked)
            Console.WriteLine(value);
    }
}

RemoveFirst(), RemoveLast() – exactly what their name suggests: removes first or last elements. Example:

using System;
using System.Collections.Generic;

class Program
{
    static void Main()
    {
        // Create a new linked list.
        LinkedList<string> linked = new LinkedList<string>();

        // First add three elements to the linked list.
        linked.AddLast("one");
        linked.AddLast("two");
        linked.AddLast("three");

        // Remove first and last elements
        linked.RemoveFirst();
        linked.RemoveLast();

        // Loop through the linked list.
        foreach (var value in linked)
            Console.WriteLine(value);
    }
}

As the previous data structures we have learned so far, Linked Lists also contain some common methods like Clear(), Contains(), CopyTo(), etc.
The most important properties of a Linked List are:

Count – returns the number of elements in the list.
First – Gets the first node of the LinkedList.
Last – Gets the last node of the LinkedList.

Comments

comments

Tags: ,

Leave a Reply