## Key Concepts

Review core concepts you need to learn to master this subject

Building blocks of a linked list

Linked List data structure

The head node in a linked list

Linked List head

Implementing a linked list

Removing a node from the middle of a linked list

Adding a new head node in a linked list

Building blocks of a linked list

Building blocks of a linked list

A linked list is a basic data structure that consists of a linear series of nodes, each of which contains data and a link to the next node. The given illustration contains an example of a linked list. The nodes are `a1`

, `a2`

, `a3`

, `a4`

, and `a5`

respectively. Each node points to the next node. The links are indicated by green arrows.

Linked List data structure

Linked List data structure

A **linked list** is a linear data structure where elements are not stored at contiguous location. Instead the elements are linked using pointers.

In a linked list data is stored in nodes and each node is linked to the next and, optionally, to the previous. Each node in a list consists of the following parts: 1) data 2) A pointer (Or reference) to the next node 3) Optionally, a pointer to the previous node

The head node in a linked list

The head node in a linked list

The first node in a linked list is referred to as the head node. In the given example, `P-i`

is the head node.

Linked List head

Linked List head

Like arrays, a **linked list** is a linear data structure. Data in a linked list is stored in the form of nodes. Each node in a list consists of the following parts:
1) data
2) A pointer (Or reference) to the next node
3) An optional pointer to the previous node

A linked list is represented by a pointer to the first node of the linked list. The first node is called head. If the linked list is empty, then the value of head is **NULL**.

Implementing a linked list

Implementing a linked list

A linked list exposes the ability to traverse the list from one node to another node. The starting node is considered the head node from where the list can be traversed.

Removing a node from the middle of a linked list

Removing a node from the middle of a linked list

When removing a node from the middle of a linked list, it is necessary to adjust the link on the previous node so that it points to the following node. In the given illustration, the node `a1`

must point to the node `a3`

if the node `a2`

is removed from the linked list.

Adding a new head node in a linked list

Adding a new head node in a linked list

When adding a new node to the start of a linked list, it is necessary to maintain the list by giving the new head node a link to the current head node. For instance, to add a new node `a0`

to the begining of the linked list, `a0`

should point to `a1`

.

- 1Linked lists are one of the basic data structures used in computer science. They have many direct applications and serve as the foundation for more complex data structures. The list is comprised …
- 2As an example, we added values to the linked list diagram from the introduction. This linked list contains three nodes (node_a, node_b, and node_c). Each node in this particular list contains a…
- 3With linked lists, because nodes are linked to from only one other node, you can’t just go adding and removing nodes willy-nilly without doing a bit of maintenance. #### Adding a new node Adding …
- 4Let’s take a minute to review what we’ve covered about linked lists in this lesson. Linked Lists: - Are comprised of nodes - The nodes contain a link to the next node (and also the previous node …

- 1Let’s implement a linked list in Python. As you might recall, each linked list is a sequential chain of nodes. So before we start building out the LinkedList itself, we want to build up a Node clas…
- 2With the Node in hand, we can start building the actual linked list. Depending on the end-use of the linked list, a variety of methods can be defined. For our use, we want to be able to: - get the…
- 3So far we can: - create a new LinkedList using .
**init**() - get the head node of the list using .get_head_node() Next up, we’ll define methods for our LinkedList class that allow us to: - insert… - 4Nice! Now we have a bunch of helpful LinkedList methods under our belt. The final use case we mentioned was the ability to remove an arbitrary node with a particular value. This is slightly more …
- 5Congratulations, you have implemented a linked list in Python! We did this by: - Defining a Node class to hold the values and links between nodes - Implementing a LinkedList class to handle extern…

## How you'll master it

Stress-test your knowledge with quizzes that help commit syntax to memory