# Synthèse - Linked Lists

## A. Glossary
> * **Embedded reference**
A reference to another object stored in an attribute of an object.

> * **Data structure**
A mechanism for grouping and organising data to make it easier to use.

> * **Linked list**
A data structure that implements a collection of elements using a sequence of linked nodes.

> * **Node**
An element of a linked list, usually implemented as an object that contains an embedded reference to another object of the same type.

> * **Cargo**
An item of data contained in a node. (The data carried by the node.)

> * **Link**
An embedded reference used to link one object to another.

> * **Fundamental ambiguity theorem**
A reference to a list node can be treated as a single object or as the first in a list of nodes.

> * **Singleton**
A linked list with a single node.

## B. Notions théoriques

> * **Qu'est-ce qu'une liste chaînée?**
A linked list is a data structure that implements a collection of elements using a sequence of linked nodes.

> * **Qu'est-ce qu'une structure de données? Donnez un exemple.**
> A data structure is a mechanism for grouping and organising data to make it easier to use. A linked list is a typical example of a data structure. It is a mechanism to group elements by organising them in a structure that can be walked through sequentially. Other examples: lists, tuples, any object...

> * **Expliquez la différence entre un noeud (Node) et sa cargaison (cargo).**
- A node is an element of a linked list, implemented as an object that contains an embedded reference to another object of the same type (the next node in the list), but that also contains a data element called its cargo.
- The cargo is only the data contained by a node, the reference to another node is a mechanism for linking nodes together.

> * **Expliquez la différence entre un noeud (Node) et une liste chainée (LinkedList).**
- A node is an object that contains a data element called its cargo, and that can be linked to another node, for example to create a linked list.
- A linked list is a collection of nodes chained together in this way. Note that nodes can also be connected in different ways, for example, to create an infinite list (which is not a valid linked list).

> * **Dans le livre, la notion d'une liste chaînée a d'abord été expliqué sans la classe LinkedList, simplement en chaînant des noeuds l'un à l'autre. Pourquoi avons nous alors besoin d'une classe LinkedList?**
- Une première raison est que la classe LinkedList nous permet de représenter de façon plus cohérente des listes vide. Si on n'a que la classe Node, une liste vide est représentée par le type None, mais avec la classe LinkedList des listes vides ou non-vides sont tous des objets de la classe LinkedList.
- Une deuxième raison est que la classe LinkedList est la classe qui représente la structure de données qu'est une liste chaînée. Elle contient la structure et les données de la chaîne, ainsi que l'ensemble de méthodes définies sur cette structure de données. On pourrait voir la classe Node comme genre de classe auxiliaire de la classe LinkedList.
> 
> 

> * __Expliquez et donnez un exemple du caractère ambiguë d'un noeud__.
> A reference to a list node object can either be treated as a single object (for exemple to get access to the data contained in its cargo) or it can be seen as a list (i.e., the list starting with that node as a first node).

> * **A linked list is a recursive data structure**
- A linked list can be regarded as a recursive data structure because it has a recursive definition.
- A linked list is either:
1. the empty list, represented by None, or;
2. a node that contains a cargo object and a reference to a linked list.
- Recursive data structures lend themselves to recursive methods.

## C. The importance of drawing