I've been reading some materials and seen a lot if talking about threaded lists. I even saw the code sample (in C) below that tried to "illustrate" what was one.
struct Node
{
int info;
struct Node *proximo;
};
What I would like to know is:
Much is already answered in What's the difference between a simply-chained and a double-chained list?
Then the linked list is the same as the linked list.
The operation of the linked list is through independent nodes where the element has the element. Each element has at least one pointer indicating where the next node is. In the double-chained list has a pointer indicating the previous node. Precisely because of this, you only know where each node is if you know where the previous one or the next one is, it can only be accessed sequentially. But because we are independent, it is easy to put what you want where you want in the middle of the list.
It is useful when you need to manipulate your elements internally, ie you need to include and / or remove items in the middle of the list simply. But you have to do this very often, if it is low, it does not usually compensate (there is always an exception). Its main feature is to be O (1) for these operations. But it has O (N) for access which is the most used operation in most situations. So it's very little used.
It has the advantage of having its elements scattered, so it is easy to manipulate the list, but it has the problem of not being a contiguous sequence, so it can not access randomly, to get the element needs to do a sequential search. This still has the problem that it is not cache friendly and the processor may have to work harder to access the elements.
In fact, in most cases where there is a need for internal manipulation of the list, it is more interesting to use a binary tree that allows you to insert and remove elements in O (logN) and access the elements in O (logN). The complexity O (logN) is very close to O (1). So today it is a very little used structure, are rare the problem where you need to manipulate internally and access only needs to be sequential. In some cases Radix may be more useful .A common mistake is to think that insertion and removal can occur at O (1) at all times. The operation alone can always occur in O (1), but you must be on the node you want to insert or remove, otherwise you will have an additional O (N) until you reach it.
Check out Big O . Remembering that these measures are always the worst case. In the linked list the average case is O (N / 2) and the best case O (1), if it is the first (last) item.
It is very common for languages to have a linked list implementation in their default library. In C # you usually do not need to make one, it already exists at LinkedList / a> ( see the source code ) that caters well almost all situations. I see only one reason why someone does it on their own if you are studying the subject, if you need something very specific (very rare) or if you think that the cost of the list has two pointers is too high to use it, then a list simply linked can be more useful (rare).
There is still circular chained list , but it is very rare to need it. It has no beginning or end, when it comes to an end, it already points to the beginning. This wiki link has a more detailed description of the whole thing.
A practical example is filesystem (having nothing to do with RAM ) and virtual memory management .
A simple and naive implementation, and without being DRY, there are a lot of methods that may be useful:
using static System.Console;
public class Node<T> {
public T Value { get; set; }
public Node<T> Next { get; set; }
}
public class LinkedList<T> {
private Node<T> head = null;
public Node<T> Add(T value) {
var node = new Node<T> {Value = value};
if (head == null) {
head = node;
} else {
var current = head;
while (current.Next != null) {
current = current.Next;
}
current.Next = node;
}
return node;
}
public T Remove(Node<T> node) {
if (head == null)
return node.Value;
if (head == node) {
head = head.Next;
node.Next = null;
return node.Value;
}
var current = head;
while (current.Next != null) {
if (current.Next == node) {
current.Next = node.Next;
return node.Value;
}
current = current.Next;
}
return node.Value;
}
public void Print() {
var current = head;
while (current != null) {
WriteLine(current.Value);
current = current.Next;
}
}
}
public class Program {
public static void Main(string[] args) {
var ll = new LinkedList<int>();
var node1 = ll.Add(1);
var node2 = ll.Add(2);
var node3 = ll.Add(3);
var node4 = ll.Add(4);
var node5 = ll.Add(5);
ll.Print();
WriteLine();
ll.Remove(node3);
ll.Print();
}
}
See running on dotNetFiddle and on CodingGround .
What is
Think of a sequence of objects of the same type, where each element is stored in a list. The first element in the first cell, the second in the second, and so on. The linked list is the representation of this sequence. It provides the basic procedures for data manipulation: insertion, removal, and fetching. Its dynamic character is one of the most important characteristics of the linked list, since it allows to store a limited number of elements only by the available memory.
Utility
Linked lists are useful when you do not know how many items will be in the list, when you do not need random access to any element, when you want to insert items in the middle of the list, and also when you need constant insertions / deletions.
The advantages of using a linked list is that the insertion or removal of an element in the list does not imply the change of place of other elements and it is not necessary to define at the time of the creation of the list the maximum number of elements that this may have. That is, it is possible to allocate memory "dynamically" only for the number of nodes needed. A manipulation becomes more "dangerous" since if the linking between elements of the list is poorly done, the whole list can be lost, making this a disadvantage of using the linked list. Another disadvantage is that to get access to the element in the n position of the list, you should go through the n - 1 above.
Example
Code in C #, removed from site .
With this implementation you can perform all the basic procedures for data manipulation (insertion, removal and search). In this code the Node class contains the Info field, to receive an object, and Next , to reference the next object in our list. The Nodes class is a collection of Node objects, which is useful for traversing the entire list. In Classes Node and Nodes we are able to store n objects in the form of a sequential list without a limit. With this optimized algorithm you can simplify the work and decrease overloads in the applications to perform certain tasks.
public class Node
{
public Node(object info, Node next)
{
this.Info = info;
Next = next;
}
public Node(object info)
{
Info = info;
Next = null;
}
public object Info = null;
public Node Next = null;
}
public class Nodes : CollectionBase
{
public Node this[int item]
{get{return this.GetNode(item);}}
public void Add(Node node)
{
List.Add(node);
}
public bool Remove(int index)
{
if (index > Count – 1 || index < 0)
return false;
else
{
List.RemoveAt(index);
return true;
}
}
private Node GetNode(int Index)
{
return (Node) List[Index];
}
}
public class ListaSimples
{
private Node Node;
public void InsereInicio(object info)
{
if(Node == null)
Node = new Node(info);
else
Node = new Node(info,Node);
}
public Node RemoveInicio()
{
Node no = null;
if(Node != null)
{
no = Node;
Node = Node.Next;
}
return no;
}
public void InsereFinal(object info)
{
if(Node == null)
Node = new Node(info);
else
{
Node nodeAux = Node;
while(nodeAux.Next != null)
{
nodeAux = nodeAux.Next;
}
nodeAux.Next = new Node(info);
}
}
public Node RemoveFinal()
{
Node no = null;
Node nodeAux;
Node nodeAux2 = new Node(null);
if(Node != null)
{
nodeAux = Node;
while(nodeAux.Next != null)
{
nodeAux2 = nodeAux;
nodeAux = nodeAux.Next;
}
no = nodeAux;
nodeAux = null;
nodeAux2.Next = null;
}
return no;
}
public Nodes Percorre()
{
Node nodeAux = Node;
Nodes nodes = new Nodes();
while(nodeAux != null)
{
nodes.Add(nodeAux);
nodeAux = nodeAux.Next;
}
return nodes;
}
public bool Busca(object info)
{
bool exists = false;
if(Node != null)
{
Node nodeAux = Node;
while(nodeAux != null)
{
if(nodeAux.Info == info)
{
exists = true;
break;
}
nodeAux = nodeAux.Next;
}
}
return exists;
}
public void Clear()
{
Node = null;
}
}
References: