14
I’ve been reading some materials and I’ve seen a lot of talk about chained lists. I even saw the code example (in C) below that tried to "illustrate" what was a.
struct Node
{
int info;
struct Node *proximo;
};
What I’d like to know is:
As my main language is C#, I would appreciate some example using it, but this is not crucial.
9
A good part is already answered in What is the difference between simply-chained and double-chained list?.
So chained list is the same as linked list (Linked list).
The functioning of the chained list is through independent nodes where has the element. Each element has at least one pointer indicating where the next node is. In the double chained list there is a pointer indicating the previous node. This is precisely why you only know where each node is if you know where the previous one is or the next one, it can only be accessed sequentially. But being independent makes it 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, i.e., you need to include and/or remove items in the middle of the list simply. But you have to do this very often, if you’re low, you don’t usually make up for it (you always have an exception). Its main feature is to be O(1) for these operations. But it has O(n) for access which is the most commonly used operation in most situations. So she’s pretty little used.
It has the advantage of having its elements scattered, and so it’s easy to manipulate the list, but it has the problem of not being a contiguous sequence, so it can’t randomly access, to get to the element it needs to do a sequential search. That 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 inserting and removing elements in O(log n) and accessing the elements in O(log n). The complexity O(log n) is very close to O(1). So today it is a very little used structure, the problems are rare where the need to manipulate internally and the access only needs to be sequential. In some cases Radix can be more useful.
A common error is that insertion and removal may occur on O(1) always. The operation alone can always occur on O(1), but you need to be at the node you want to insert or remove, otherwise you will have an additional O(n) until you get to it.
See about Big O. Remembering that these measures are always the worst case. In 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 chained list implementation in their standard library. In C# in general you do not need to make one , already exists the LinkedList (see the source code) that takes good care of almost every situation. I only see why someone should do it on their own if they are studying the subject, if they need something very specific (very rare), for example if they think that the cost of having two pointers is too high to use it, then a simply linked list may be more useful (rare).
There is still the use of circular chained list, but it is very rare to need. It has no beginning or end, when it comes to the end, it already points to the beginning. This link of Wikipedia has a more detailed description on the whole subject.
A practical example is the filesystem (has nothing to do with RAM) and the virtual memory management.
A simple and very naïve implementation and without being DRY, many methods are missing 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();
}
}
Behold working in the ideone. And in the .NET Fiddle. Also put on the Github for future reference.
5
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. A chain list is the representation of this sequence. It offers the basic procedures for data manipulation: insertion, removal and search. Its dynamic character is one of the most important characteristics of the chained list, as it allows storing a number of elements limited only by the available memory.
Usefulness
Chained lists are useful when you don’t know how many items will be in the list, when you don’t 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/exclusions.
The advantages of using a chained 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 it 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 chaining (linking) between list elements is poorly done, the whole list can be lost, making it a disadvantage of using the chained list. Another disadvantage is that to have access to the element in position n of the list, the n - 1 previous.
Example
Code in C#, taken from this website.
With this implementation all basic procedures for data manipulation (insertion, removal and search) can be performed. In that code the class Node contains the field Info, to receive an object, and Next, to reference the next object in our list. The class Nodes is a collection of objects Node, which is useful for going through the whole list. In Classes Node and Nodes we can store n objects in the form of a sequential list without a limit. With this optimized algorithm one can simplify the work and decrease overloads 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:
Browser other questions tagged terminology chain-list
You are not signed in. Login or sign up in order to post.