Section 16b

Adding Items to a Linked List


 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Linking Data In

Overview

There are fundamentally three ways to add data (nodes) to a linked list. There is adding or linking, at the head, linking at the end, called appending, and linking anywhere else in the list, which is commonly called inserting. This topic will look at each of these briefly in the text but at length in the videos. There won't be a lot of code provided because the code itself is pretty simple once you draw the pictures and understand the actions. None of these operations are terribly complicated but they all need the more dynamic presentation that the videos provide. Make sure you watch the videos with paper and pencil nearby. There will be lots of opportunities to draw those pictures.

Adding A Node At The Head

You have seen part of this process in the previous topic, but there is a little more to it. In the previous situation, the list was empty, and in fact, that is a valid circumstance to consider. However, the alternative to that scenario is that the list already has data in it, but for whatever reason, the data is to be inserted at the head and before all the remaining data.

Take a look at a linked list already developed.

linked list

As you have seen before, you can set another reference to the first node, as shown here.

linked list with working reference

Now you can assign the head reference to another node, as you have seen previously.

head reference with one node

And finally, you assign the new node's next reference to the working reference's remaining list, as shown.

first node and list linked

That's about all there is to it. There are other ways to do this but the bottom line is that you must maintain a link to the list so you can come back and link it to the new node.

Adding A Node At The End - Appending

Appending is not much more difficult. The process needs to iterate across the list until it gets to the end and then link the last nextRef to a new node. And that's it. Check out this video, with pencil and paper at hand

Inserting Into A Linked List

So far adding nodes to a linked list has not been difficult. The insertion process is slightly more complicated but again as long as you can draw on paper what you want to accomplish, you will find that it translates very easily to code. Check out this video to see the action. Note that the video shows searching for the location to insert but remember you also have to make sure the node you are at is not null (i.e., you have not found the end of the linked list).

Copying A Linked List

As mentioned, There are really just three ways to add a node or data to a linked list. However, sooner or later, you will find yourself copying one linked list to another one. Although there are other circumstances where you might be copying a linked list, the most likely condition will be in a copy constructor of a linked list class. The good news here is that while it is handy to know how to do this particular action, it is also very helpful in understanding how linked lists work to see the mechanics of this process. Once again, make sure your pencil and paper are right at hand, and take a look at this video.