How to Reverse a Linked List in Python, Java, and C++
If you have ever taken a Data Structures and Algorithms course or prepared for a technical interview that involves programming, you are likely familiar with the concept of linked lists. You can use linked lists to create many other data structures, such as stacks, queues, and trees, and generally its very commonly used for dynamic memory allocation. For more specific uses, it can be utilized to represent polynomial manipulation or even simply a mailing list for emails. Today I will give a brief overview of what a linked list is and then showcase how to reverse a linked list in Python, Java, and C++.
A linked list is a linear data structure, which means the elements are not stored in contiguous memory locations, but instead are linked using pointers. The linked list consists of nodes that contain data and a reference to the next node in the list.
Today we will be reversing a linked list. The input and output of the program is fairly simple to visualize. If the input is 1,2,3,4 then our corresponding output is 4,3,2,1.
First we are going to create a static variable called "head" that is of the type Node. The name head refers to the head of the linked list that will then point to the following nodes within the linked list. For those who are less familiar with Java, static means that a single copy of the variable is being created and it can be used to refer to a common property of all objects within the program.
We then are going to create a static class called Node. We will create a variable of type int, called data, which is the data that will be stored in the nodes of the linked list. We will also be creating another variable of type Node called next, used to refer to the next node in the linked list.
We will also create a Node constructor that accepts an integer as its argument. The data variable is initialized to the value of the given argument and next is initialized to null.
Now lets create another method called reverse. This is what we will be using to reverse the linked list. The class will be returning a variable of type node, so we start the class by saying Node as well. It also requires an argument of a variable of type Node so we put that in brackets. When this class is called, a variable of type Node called previous, will be set to null. The current variable of type node will be set to the argument when this class is called. A variable of type Node called next will also be set to null.
Now in this while loop is where the reversing will occur and we are specifically using the iterative method of reversing a linked list. Before changing next of current, it stores next node. Then change next of current. Then you move previous and current one step forward.
Now moving on to a print method, lets call it printList. It will not return any variables so its a void method however it requires a node type variable to call this method. While node is not equal to null, which is the end of the linked list, we print out the data stored within it, so the aforementioned integer values. Then it moves to the next node until we get to the end of the linked list.
Finally we need a driver method so just our classic public static void main method. We will first create a new object of the LinkedList class called list so we can access it.
Here we input the data values of all the nodes in this linked list, and we just .next to go each successive node. Now lets print both the given linked list and the reversed linked list. First we print the current linked list. Then we will reverse it using the reverse method we created earlier and store the node it returns in the old head variable. Now if we print the list using the same print function, it prints the reversed link list.
Now the logic for both the Python and C++ versions of the code is the same. Just some different syntax.
