TECHY360
Everything You Need To Know About Tech
0 25

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.

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 `ProcessItems`at 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 ;
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.

```
{
while (true)
{
int value = NextValue ();
if (value! = 0xFFFF)
{
}
else
{
break;
}
}

ProcessItems (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 interface`IEnumerable`

### 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 `Node`can 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 ( `first``middle``last`) 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 `first`and to `last`. The `Next`last 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 `PrintList`iterated over the elements of the list: prints the value of the field `Value`and 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`.

```
{
///
/// Constructor of a new node with the Value 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; }
}
```

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
{
{
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;
}

{
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();
}
}
```

• 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 `Next`last 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 `Add`will 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;
```

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

```public void Add(T value)
{

{
_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 `_head`and `_tail`so 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 `_tail`now points to the new end of the list.

The field is `Count`incremented 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 `true`if the item has been deleted and `false`otherwise.
• Difficulty: O (n)
Related Posts
1 of 8

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 `Next`with 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 `Next`previous 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 `_head`and `_tail`equal `null`.
• The deleted node will be at the top of the list. In this case, we write the `_head`link 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 `_tail`link to the penultimate node, and `Next`write it in its field `null`.
```public bool Remove(T item)
{

// 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

// Head -> 3 -> null

// Is the list empty now?
{
_tail = null;
}
}

Count--;

return true;
}

previous = current;
current = current.Next;
}

return false;
}
```

The field is `Count`decremented when a node is deleted.

### Contains method

• Behavior: Returns `true`or `false`depending on whether the item you are looking for is in the list.
• Difficulty: O (n)

The method is `Contains`quite simple. It scans every element of the list, from the first to the last, and returns `true`as 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)
{
while (current != null)
{
if (current.Value.Equals(item))
{
return true;
}

current = current.Next;
}

return false;
}
```

### GetEnumerator method

• Behavior: Returns an instance `IEnumerator`that 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()
{
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 `Clear`simply sets the values of fields `_head`and `_tail`equal `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()
{
_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 `CopyTo`goes 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)
{
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 `Add``Remove`and `Clear`.

```public int Count
{
get;
private set;
}
```

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

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 `LinkedListNode`field to the class `Previous`that 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 `LinkedListNode`is to add a field with a link to the previous node.

```public class LinkedListNode
{
//
// Constructor of a new node with the Value 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; }
}
```

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 `AddFirst`and, `AddLast`accordingly. The method `ICollection<T>.Add`will call `AddLast`for 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 `Next`in the new node so that it points to the former first node.
2. Set the field value `Previous`in the former first node so that it points to the new node.
3. Update the field `_tail`if necessary and increment the field`Count`
```
{

// Save the link to the first item.

// _head points to the new node.

// Insert the list behind the first item.

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

Count ++;
}
```

• 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 `_head`and `_tail`then increment the field `Count`.

```public void AddLast (T value)
{

if (Count == 0)
{
}
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>.Add`just calling `AddLast`.

```public void Add(T value)
{
}
```

### RemoveFirst method

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

• Behavior: Removes the first item in the list. If the list is empty, do nothing. Returns `true`if the item has been deleted and `false`otherwise.
• Difficulty: O (1)

`RemoveFirst`establishes a link `head`to the second node of the list and resets the field of `Previous`this node, thus removing all references to the previous first node. If the list was empty or contained only one element, then the fields `_head`and `_tail`become equal `null`.

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

// Head -> 3 -> null

Count--;

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

### RemoveLast method

• Behavior: Removes the last item in the list. If the list is empty, do nothing. Returns `true`if the item has been deleted and `false`otherwise.
• Difficulty: O (1)

`RemoveLast`sets the field value `_tail`so 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 `_head`and `_tail`become equal `null`.

```public void RemoveLast ()
{
if (Count! = 0)
{
if (Count == 1)
{
_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 `true`if the item has been deleted and `false`otherwise.
• 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 `Previous`when deleting a node. In order not to repeat the code, this method calls `RemoveFirst`when deleting the first node.

```public bool Remove(T item)
{

// 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 `head`and `tail`, the user of our list will be able to implement many different algorithms.

```public LinkedListNode Head
{
get
{
}
}

{
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 `Tail`and `Previous`to get around the list backwards.

```public void ProcessListBackwards()
{
PopulateList(list);

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.