LinkedList Generic Class

Represents a doubly linked list.

Namespace: System.Collections.Generic
Assembly: System (in system.dll)

[SerializableAttribute] 
[ComVisibleAttribute(false)] 
generic<typename T>
public ref class LinkedList : ICollection<T>, IEnumerable<T>, 
	ICollection, IEnumerable, ISerializable, IDeserializationCallback
J# supports the use of generic types and methods, but not the declaration of new ones.
JScript does not support generic types and methods.
Not applicable.

Type Parameters

T

Specifies the element type of the linked list.

LinkedList is a general-purpose linked list. It supports enumerators and implements the ICollection interface, consistent with other collection classes in the .NET Framework.

LinkedList provides separate nodes of type LinkedListNode, so insertion and removal are O(1) operations.

You can remove nodes and reinsert them, either in the same list or in another list, which results in no additional objects allocated on the heap. Because the list also maintains an internal count, getting the Count property is an O(1) operation.

Each node in a LinkedList object is of the type LinkedListNode. Because the LinkedList is doubly linked, each node points forward to the Next node and backward to the Previous node.

Lists that contain reference types perform better when a node and its value are created at the same time. LinkedList accepts a null reference (Nothing in Visual Basic) as a valid Value property for reference types and allows duplicate values.

If the LinkedList is empty, the First and Last properties contain a null reference (Nothing in Visual Basic).

The LinkedList class does not support chaining, splitting, cycles, or other features that can leave the list in an inconsistent state. The list remains consistent on a single thread. The only multithreaded scenario supported by LinkedList is multithreaded read operations.

The following code example demonstrates many features of the LinkedList class.

#using <System.dll>

using namespace System;
using namespace System::Text;
using namespace System::Collections::Generic;

void Display(LinkedList<String^>^ words)
{
    for each( String^ word in words )
    {
        Console::Write(word + " ");
    }
    Console::WriteLine();
};
    
void DisplayNode(LinkedListNode<String^>^ node)
{
    if (node->List == nullptr)
    {
        Console::WriteLine("Node \"{0}\" is not in a list.", 
            node->Value);
        return;
    }

    StringBuilder^ result = gcnew StringBuilder("(" + node->Value + ")");
    LinkedListNode<String^>^ nodeP = node->Previous;

    while (nodeP != nullptr)
    {
        result->Insert(0, nodeP->Value + " ");
        nodeP = nodeP->Previous;
    }

    node = node->Next;
    while (node != nullptr)
    {
        result->Append(" " + node->Value);
        node = node->Next;
    }

    Console::WriteLine(result);
};

void main()
{
    array<String^>^ words = 
        {"the", "fox", "jumped", "over", "the", "dog"};
    LinkedList<String^>^ sentence = 
        gcnew LinkedList<String^>((IEnumerable<String^>^) words);
    Display(sentence);

    Console::WriteLine("sentence->Contains(\"jumped\") = {0}", 
        sentence->Contains("jumped"));

    // Add the word "today" to the beginning of the linked list.
    // Remove the new node, and add it to the end of the list.
    sentence->AddFirst("today");
    Display(sentence);

    LinkedListNode<String^>^ mark1 = sentence->First;
    sentence->RemoveFirst();
    sentence->AddLast(mark1);
    Display(sentence);

    sentence->RemoveLast();
    sentence->AddLast("yesterday");
    Display(sentence);

    mark1 = sentence->Last;
    sentence->RemoveLast();
    sentence->AddFirst(mark1);
    Display(sentence);

    sentence->RemoveFirst();

    LinkedListNode<String^>^ current = sentence->FindLast("the");
    DisplayNode(current);

    sentence->AddAfter(current, "old");
    sentence->AddAfter(current, "lazy");
    DisplayNode(current);

    current = sentence->Find("fox");
    DisplayNode(current);

    sentence->AddBefore(current, "quick");
    sentence->AddBefore(current, "brown");
    DisplayNode(current);

    // Keep a reference to the current node, "fox", and to the
    // previous node in the list. Use the Find method to locate
    // the node containing the value "dog". Show the position.
    mark1 = current;
    LinkedListNode<String^>^ mark2 = current->Previous;
    current = sentence->Find("dog");
    DisplayNode(current);

    // The AddBefore method throws an InvalidOperationException
    // if you try to add a node that already belongs to a list.
    try
    {
        sentence->AddBefore(current, mark1);
    }
    catch(InvalidOperationException^ ex)
    {
        Console::WriteLine("Exception message: {0}", ex->Message);
    }

    // Remove the node referred to by mark1, and add it before 
    // the node referred to by current. Show the sentence, 
    // highlighting the position of the node referred to by
    // current.
    sentence->Remove(mark1);
    sentence->AddBefore(current, mark1);
    DisplayNode(current);

    // Remove the node referred to by current. If you try to show
    // its position now, the DisplayNode method prints a message.
    // Add the node after the node referred to by mark2, and 
    // display the sentence, highlighting current.
    sentence->Remove(current);
    DisplayNode(current);
    sentence->AddAfter(mark2, current);
    DisplayNode(current);

    // The Remove method finds and removes the first node that 
    // that has the specified value.
    sentence->Remove("old");
    Display(sentence);

    // When the linked list is cast to ICollection(Of String),
    // the Add method adds a node to the end of the list. 
    sentence->RemoveLast();
    ICollection<String^>^ icoll = sentence;
    icoll->Add("rhinoceros");
    Display(sentence);

    // Create an array with the same number of elements as the
    // linked list.
    Console::WriteLine("\nCopy the list to an array.");
    array<String^>^ sArray = gcnew array<String^>(sentence->Count);
    sentence->CopyTo(sArray, 0);

    for each( String^ s in sArray )
    {
        Console::WriteLine(s);
    }

    // Release all the nodes.
    sentence->Clear();
}

//This code example produces the following output:
//
//the fox jumped over the dog
//sentence->Contains("jumped") = True
//today the fox jumped over the dog
//the fox jumped over the dog today
//the fox jumped over the dog yesterday
//yesterday the fox jumped over the dog
//the fox jumped over (the) dog
//the fox jumped over (the) lazy old dog
//the (fox) jumped over the lazy old dog
//the quick brown (fox) jumped over the lazy old dog
//the quick brown fox jumped over the lazy old (dog)
//Exception message: The LinkedList node belongs a LinkedList.
//the quick brown jumped over the lazy old fox (dog)
//Node "dog" is not in a list.
//the quick brown (dog) jumped over the lazy old fox
//the quick brown dog jumped over the lazy fox
//the quick brown dog jumped over the lazy rhinoceros
//
//Copy the list to an array.
//the
//quick
//brown
//dog
//jumped
//over
//the
//lazy
//rhinoceros

System.Object
  System.Collections.Generic.LinkedList

This type is not thread safe. If the LinkedList needs to be accessed by multiple threads, you will need to implement their own synchronization mechanism.

A LinkedList can support multiple readers concurrently, as long as the collection is not modified. Even so, enumerating through a collection is intrinsically not a thread-safe procedure. In the rare case where an enumeration contends with write accesses, the collection must be locked during the entire enumeration. To allow the collection to be accessed by multiple threads for reading and writing, you must implement your own synchronization.

Windows 98, Windows Server 2000 SP4, Windows CE, Windows Millennium Edition, Windows Mobile for Pocket PC, Windows Mobile for Smartphone, Windows Server 2003, Windows XP Media Center Edition, Windows XP Professional x64 Edition, Windows XP SP2, Windows XP Starter Edition

The Microsoft .NET Framework 3.0 is supported on Windows Vista, Microsoft Windows XP SP2, and Windows Server 2003 SP1.

.NET Framework

Supported in: 3.0, 2.0

.NET Compact Framework

Supported in: 2.0

XNA Framework

Supported in: 1.0

Community Additions

ADD
Show: