Practice: Inserting Elements in a Linked List

Introduction

To practice working with pointers and linked lists, we’ll implement a few functions, which are usually part of the linked list data structure.

It’s crucial to make memory drawings. Draw an example list and do the pointer manipulations on paper. See which pointer needs to point where and how the result should look. Get into the habit of creating memory drawings, and you’ll be able to solve any linked list problem, no matter the difficulty.

Insert at the beginning of a list

Let’s explore the problem of inserting an element at the beginning of a linked list.

Problem statement

Inserting elements at the beginning of a linked list is one of the basic operations of this data structure.

Assume we have the list [1, 2, 3] and we want to insert 10 at the beginning. The result will be [10, 1, 2, 3].

Similarly, if we have an empty list [] and want to insert 10 at the beginning, we’ll obtain the list [10].

**Note: **Recall that some functions are provided, in the background, by the environment, such as allocNode, createExampleList, printList and freeList.

We’ll write a function called insertFirst, which takes a linked list and a value as arguments. It will construct a new node for that value and insert it at the beginning of the list.

Solution

Let’s think about how inserting an element at the beginning changes the list.

Say our initial list is [1, 2, 3], with the head node [1]. After inserting 10, the list becomes [10, 1, 2, 3] with the head node 10. The consequence is that we have to update the pointer we’re using to access the list. See the following drawing for clarification.