# Singly Linked Lists - Insertion

Given the structure of our linked list, we can easily insert a new node at any location in the list. However, for our purposes we are generally interested in inserting new nodes at the beginning of the list, at some specific location in the list, or in the appropriate order if the list is sorted.

## Inserting at the Beginning

Inserting a node at the beginning of a list is straightforward. We just have to be careful about the order we use when swapping pointers. In the `prepend`

code below, line 1 creates the new node to be stored in the list. Next, line 2 assigns the pointer in the new node to point to the pointer held by the `head`

. If there was an item already in the list, `head`

will point to the previous first item in the list. If the list was empty, `head`

will have been `null`

and thus the `node.next`

will become `null`

as well. Line 3 assigns `head`

to point to the new node and line 4 increments our size variable.

```
function prepend(data)
node = new Node(data) (1)
node.next = head (2)
head = node (3)
size = size + 1 (4)
end function
```

We show this process in the following example. The figure below shows the initial state as we enter the `prepend`

operation. Our list has three items in it, an “a”, “W”, and “Q” and we want to add the new node “M” in front of item “a”.

The figure below shows the effect of the first step of the operation. This step creates a new node for “M” and changes `next`

to point at the same node as the pointer held by `head`

, which is the address of the first item in the list, “a”.

The result of performing line 3 in the operation is shown below. In line 3 we simply change `head`

to point to our new node, instead of node “a”. Notice now that the new node has been fully inserted into the list.

And, if we redraw our diagram a bit, we get a nice neat list!

Since there are no loops in the `prepend`

operation, `prepend`

runs in constant time.

## Inserting in the Middle

Inserting a node at a given index in the linked list is a little more difficult than inserting a node at the beginning of the list. First, we have to find the proper location to insert the new node before we can actually insert it. However, since we are given an index number, we simply need to follow the linked list to the appropriate index and then perform the insertion.

We do have a precondition to meet before we proceed, however. We need to make sure that the index provided to the operation is not less than 0 and that it is not greater than the size of the list, which is checked in line 2. If the precondition is not satisfied, we raise an exception in line 3.

```
function insertAt(data, index) (1)
if index < 0 or index > size (2)
raise exception (3)
elseif index == 0 (4)
prepend(data) (5)
else
curr = head.next (6)
prev = head (7)
node = new Node(data) (8)
for i = 1 to index – 1 (9)
prev = curr (10)
curr = curr.next (11)
end for (12)
prev.next = node (13)
node.next = curr (14)
size = size + 1 (15)
end if
end function
```

Lines 4 and 5 check to see if the `index`

is 0, which means that we want to insert it as the first item in the list. Since this is the same as the `prepend`

operation we’ve already defined, we simply call that operation. While this may not seem like a big deal, it is actually more efficient and helps us to simplify the code in the rest of the operation.

The operation uses `curr`

to keep track of which node in the list we are currently looking at, thus we initialize `curr`

to point at the first node in the list in line 6. To allow us to swap pointers once we find the appropriate place in the list, we keep track of the node previous to `curr`

as well by using the variable `pre`

. This variable is initialized to `head`

in line 7, and line 8 creates the new node we will insert into our list. After line 8, our `list`

, `node`

, and `previous`

pointers would look like the following (assuming the index passed in was `2`

).

At this point we start our walk through the list using the `for`

loop in lines 9 - 12. Specifically, with an `index`

of 2 we will actually go through the loop exactly one time, from `1 to 1`

. Each time through the loop, lines 10 and 11 will cause `curr`

and `prev`

to point at the next nodes in the list. At the end of one time through our loop, our example will be as shown below.

Now, the only thing left to do is update the `next`

pointer of node “3” to point at `node`

(line 13), and `node.next`

to point at `curr`

node (line 14), while line 15 increments the size attribute. The updated list is shown below.

The `insertAt`

operation, while being quite flexible and useful, can potentially loop through each node in the list. Therefore, it runs in order $N$ time.

## Inserting in Order

When we want to insert an item into an ordered list, we need to find the right place in the list to actually insert the new node. Essentially, we need to search the list to find two adjacent nodes where the first node’s data is less than or equal to `data`

and the second node’s data is greater than `data`

. This process requires a linear search of the list.

```
function insertOrdered(data)
curr = head (1)
index = 0 (2)
while curr != NULL AND curr.data < data (3)
index = index + 1 (4)
curr = curr.next (5)
end while
insertAt(data, index) (6)
end function
```

Notice that we do not have a precondition since we will search the list for the appropriate place to insert the new node, even if the list is currently empty. In line 1, we create a `curr`

variable to point to the current node we are checking in the list, while in line 2 we initialize an `index`

variable to keep track of the index of `curr`

in the list.

Next, lines 3 – 5 implement a loop that searches through the list to find a node where the data in that node is greater than or equal to the data we are trying to put into the list. We also check to see if we are at the end of the list. Inside the loop, we increment `index`

and point `curr`

to the next node in the list.

Once we find the appropriate place in the list, we simply call the `insertAt`

operation to perform the actual insertion. Using the `insertAt`

operation provides a nice, easy to understand operation. However, we do suffer a little in efficiency since both operations loop through the list to the location where we want to insert the new data node. However, since the `insertAt`

call is not embedded within the loop, our `insertOrdered`

operation still runs in order $N$ time.

Since the previous example inserts the number 2 into the list (which falls between -1 and 3), the results of running the `insertOrdered`

operation will be the same output as the result of the `insertAt`

operation as shown above.