Singly Linked Lists Definition

Motivation

In this chapter, we’ll discuss singly linked lists. One may be surprised why we discuss data structure in a course about pointers and memory management. The answer is that we aren’t interested in the data structure itself. We are interested in implementing it from scratch because it’s good practice for working with pointers and dynamic memory allocations.

The functions on linked lists are conceptually simple, but they often require memory drawings and paying attention to how to manipulate the pointers correctly. Usually, we don’t have to write a lot of code. However, the code we write is challenging from the point of view of the pointers.

Linked list introduction

There are more list types, such as singly linked lists, doubly linked lists, circular lists, generic lists, etc. In this chapter, we’ll discuss singly linked lists. The elements from a linked list are called nodes. Each node holds the value for that element and a pointer to the next element inside the list.

Intuitively, we can view a linked list like in the widget below. For example, each node holds a value (1, 2, 3, 4, or 5), and each node points to the next node, except the last node, which doesn’t point anywhere (since it is the last node).