Algorithm - Contiguous and Chained Lists

Why lists?

Lists are often found in everyday life such as:

Individuals in a waiting room.
Students enrolled in a specialty.
Cars are waiting for the red light.
etc.

The goal is to represent these real-life examples and process them in computer science.

What are the characteristics of a list?

They are processed sequentially.
Delimited by both ends < head> and < queue>.
It is possible to add or remove elements.
Dynamic structure (size varies).

Representation

1 - Contiguous representation

We have seen that we can represent a list with an array T[1..max] but its structure is static (its size is fixed at the time we define the in the declaration).

list type: Article
{
T: array[1..lmax] of element
length: 0..lmax
}

Most important operations

Le parcours

Procedure path(L:list)
Start
for i from 1 to L.length
faire
process(L.T[i])
finfaire
End

Deletion ( see: s deletion of an item from a contiguous list).

The insertion (see: Inserting an Item into a List contiguous).

The advantages

Direct access.
Deletion and insertion at the end of the list.
Easy implementation.

Cons

You have to know how to change the length.
Deletions and insertions involve offsets.

2- Representation chained

It is composed of a sequence of links (blocks) and each link consists of two fields:

An element field.
An address field that points to the following.

L: pointer to the first link.

An empty linked list is represented by L=null.

ptr type: link pointer

link type: article

{

valley; element

link: ptr

}

chainlisted< type: link/span>

var L: chainlisted

Most important operations

The course.

Procedure path(L:list)
Top
pp := L.link // Head de L
as long as pp != null
faire
treat(L.T[i])
pp := *pp.link
finfaire
Fin

Suppression(see: Inserting and deleting an item in a linked list.).

Insertion(see: Inserting and deleting an item in a linked list.).

Advantages

Sequential path.
Removed a link.
Inserting a link.

Cons

Indirect access to an element, you have to go through i-1 links to reach the i^th maillon.
Loss of memory space for links.