In this post, we will explain What is Linked List, which is one of the known types in the linear data structure, we will also learn How to use Linked List using C#?
Note: It's recommended reading Introduction to Data Structure to understand what is data structure.
What is Linked List in data structure?
A Linked List is a linear data structure, which connected together via links.
- A linked list is a sequence of links that contain items. Each contains a connection to another link.
- Linked List is the second most used in data structure after Array.
Unlike the array, it is not sequential in the memory, so who knows the item in the memory is linked list?
Each item contains two things:
- Element: contain the data.
- Pointer: contain the address of the next item in the linked list.
So the container which contains the element, a pointer called Node. The below figure explains more.
Syntax:
var myList = new LinkedList<String>();
How does a linked list work in data structure?
The strong feature of Linked List is that is not sequential in the memory, so
- If add in the first of the List all that I need is the new pointer of the item point to the first item in the current List.
- And if add at the end of the List all that I need is to change the previse pointer from null to the new address of the added item.
- And if add in the middle of List change the previse pointer to the new item, the new item pointer pointe to the next item.
This animation explains how dose linked list works:
When to use Linked List in data structure?
In Data Structure, you may need to use the Linked List in the following cases:
- You don't know how many items will be on the list.
- You don't need random access to any elements.
- You want to be able to insert items in the middle of the list.
Type of Linked list:
Following are the various types of linked lists.
- Simple Linked List − Item navigation is forward only.
- Doubly Linked List − Items can be navigated forward and backward.
- Circular Linked List − The last item contains a link of the first element as next and the first element has a link to the last element as previous.
Linked list methods in C#
In this section, we will talk about the methods in C#.
1) Add methods:
The linked list provides four methods to add nodes in Linked List and they are:
- AddFirst: add in the first list.
- AddLast: add in the first list.
- AddBefore: add before an existing node in the list, has two parameters one for the existing node, second the value of the new node.
- AddAfter: add after an existing node in the list, has two parameters one for existing node, second the value of the new node.
2) Remove methods:
The linked list provides four methods to remove nodes in Linked List and they are:
- Remove(): remove the existing node from the list, overload remove by the value that finds first in the list.
- RemoveFirst(): remove in the first node of the list.
- RemoveLast(): remove in the last node of the list.
- Clear(): remove all the nodes in the list.
Example: Implementing Code of the Linked list in C#
In this example, you will learn How to create a Linked List in C#, and How to add items to your Linked List at specific places.
var myList = new LinkedList<int>();
myList.AddFirst(1); // add in the first of the list
myList.AddLast(2); // add in the last of the list
myList.AddLast(3); // add in the last of the list
myList.AddAfter(myList.First,10); // add before the first node
myList.AddBefore(myList.Find(3), 20); // add after the node that contain value 3
Console.WriteLine("Elements in the list:");
foreach (var item in myList)
Console.WriteLine(item);
Output
Elements in the list:
1
10
2
20
3
References:
