Operation 2  Insert Node :

Insert Node adds data to a linked list. We need only its logical predecessor to insert a node into the list. Given the predecessor, there are three steps to the insertion :

1. Allocate memory for the new node and insert data.

2. Point the new node to its successor.

3. Point the new node’s predecessor to the new node.

These steps appear to be simple, but a little analysis is needed to fully understand how to implement them. To insert a node into a list we need to know the location of the node that precedes the new node. This node is identified by a pointer that can be in one of two states : it can contain the address of a node or it can be null. When the predecessor is null, it means that there is no predecessor to the data being added. The logical conclusion is that we are either adding to an empty list or are at the beginning of the list. If the predecessor is no null, then we are adding somewhere after the first node – that is, in the middle of the list or at the end of the list. Let’s discuss each of these situations in turn.

Operation 2a ¾ Insert into Empty List :

When the head pointer of the list is null, then the list is empty. This situation is shown in Figure 11. All that is necessary to add a node to an empty list is to assign the list head pointer the address of the new node and make sure that its link field is a null pointer. Although we could use a constant to set the link field of the new node, we use the null pointer contained in the list head. Why we use the list head null pointer will become apparent in the next section.

Node the order of these two statements. We must first point the new node to its successor; then we can change the head pointer. If we reverse these statements, we will end up with the new node pointing to itself, which would put our program into a never-ending loop when we process the list.

Operation 2b ¾ Insert at Beginning :

We add at the beginning of the list anytime we need to insert a node before the first node of the list. We determine that we are adding at the beginning of the list by testing the predecessor pointer. If it is a null pointer, then there is no predecessor so we are at the beginning of the list.

To insert a node at the beginning of the list we simply point the new node to the first node of the list and then set the head pointer to point to the new first node. We know the address of the new node. The question at this point is how we can find the address of the first node currently in the list so we can point the new node to it. The answer is simple. The first node’s address is stored in the head pointer. The pseudocode statements to insert at the beginning of the list are shown in the inset of figure 12.

If you compare these two statements with the statements to insert into an empty list, you will see that they are the same. They are the same because, logically, inserting into an empty list is the same as inserting at the beginning of a list.

Operation 2c ¾ Insert in Middle :

When we add a node anywhere in the middle of the list, the predecessor contains an address. This case is shown in Figure 13.

To insert a node between two nodes, we point the new node to its successor and then point its predecessor to the new node. The address of the new node’s successor can be found in the predecessor’s link field.

Operation 2d ¾ Insert at End :

When we are adding at the end of the list, we only need to point the predecessor to the new node. There is no successor to point to. It is necessary, however, to set the new node’s link field to a null pointer. The statements to insert a node at the end of a list are shown below in the inset of figure 14.

We can take advantage of the existing linked list structure. We know that the last node in the list will have a null link pointer. If we use this pointer rather than a null pointer constant, then the code becomes exactly the same as the code for inserting in the middle of the list.

General Insert Node Algorithm :

Now let’s write the algorithm that puts it all together and inserts a node into the list. We are given the head pointer, the predecessor, and the data to be inserted. We allocate memory for the new node and adjust the link pointers appropriately. When the algorithm is complete, it returns a Boolean – true if it was successful and false if there was no memory for the insert. The pseudocode is found in Algorithm 2.

Algorithm – 2 Insert linked list node

algorithm insertNode (ref list ,

val pPre ,

val dataIn )

Inserts data into a new node in the linked list.

Pre list is metadata structure to a valid list

pPre is pointer to data’s logical predecessor

dataIn contains data to be inserted

Post data have been inserted in sequence

Return true if successful, false if memory overflow

1 allocate (pNew)

2 if (memory overflow)

1 return false

3 end if

4 pNew->data = dataIn

5 if (pPre null)

Adding before first node or to empty list.

1 pNew->link = list. head

2 list. head = pNew

6 else

Adding in middle or at end.

1 pNew->link = pPre->link

2 pPre->link = pNew

7 end if

8 list.count = list.count + 1

9 return true

10 end insertNode