Sunday, June 23, 2024 20:28

Table of contents >> Data Structures > Linked List

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.

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:

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:

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

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.

Tags: ,

Leave a Reply

Follow the white rabbit