Let's Learn!

Rearranging list nodes is confusing. What's a node's .next? How do I get from the before to the after picture? Use this website to answer those questions and more!

An Introduction

Let's take a moment to look at a basic ListNode class:

We can see that within the class, we have two fields: data and next. The field data represents the int that each ListNode holds, while the field next holds a reference to the next ListNode. In the example below, data is equal to "0" and next is equal to "null". Note that it's possible for the ListNode to not be pointing to another ListNode, which is when the next field will be equal to null.

Here's an example in which list.next actually holds another ListNode:

If we wanted to write code to create this linked list, we would use:

ListNode list = new ListNode(3, new ListNode());

Arrays vs. Linked Lists

So why should we care about linked lists? Aren't arrays good enough? Well, yes and no! There are certain advantages/disadvantages to using a linked list and certain advantages/disadvantages to using an array.

Let's start with arrays! Arrays allow us to use something called "random access," which means that we can instantly access the element at any index very quickly (as long as that index is legal). To get the value at the third index, we can just use arr[2]. However, arrays have a fixed size. Whatever size we declare our array to have is the one that it will continue to have, which may be a problem if we even want to decrease/increase the size.

Now onto everyone's most (least?) favorite data structure- linked lists! Linked lists do not have the advantage of random access; in order to access an element at a certain index, you need to include that many calls to .next. You can think of it like having to fast-forward through a cassette tape: we can't just skip from song to song, we have to manually iterate the entire length of the song. If we wanted to access the node with 7 in it, we would have to use list.next.next. But, linked lists can change size! Because of their nature, we can just change which list node is being referencing to by a previous list node in order to insert/delete elements.

Rearranging References

Next, we'll dive into some interesting problems called "neighborhood problems." When doing these, we get a before and an after picture and have to figure out what code is necessary in order to get our before picture to look like our after pucture.