CSCI 136 - Spring 2026

Data Structures

Home | Lectures | Labs | Handouts | CS@Williams

Lab 3: Linked Lists

This lab is about getting practice with ArrayLists, Singly Linked Lists, and Doubly Linked Lists.

Obtaining the Starter Code

Open your terminal using Control-` (this is a backtick, not an apostrophe: the key is above your Tab key). Type git pull and then hit enter.

Once you have run the git pull command, use VSCode to open the Lab03 folder in your repo. (Remember to use Open Folder, and not Open File.) You should see some familiar files: ArrayListInt.java, IntNode.java, LinkedListInt.java, DLLNodeInt.java, and DoublyLinkedListInt.java

Task 0: Concatenation

In the following, we will look at the differences in concatenating different kinds of lists. Concatenating two lists means joining them: so if we have a list [1,2,3], and call concat([4,5,6]) (that is to say: the argument to concat is a list containing [4,5,6]) we will get a list: [1,2,3,4,5,6].

In all cases, our method will be called concat() and will have a void return type. The parameter to the method will be the list we want to join to the end of the current list.

This task is just about getting on the same page about what concatenation is. You're all done!

Task 1: Concatenating an ArrayList

Write a method in ArrayListInt.java called: public void concat(ArrayListInt otherList) that concatenates otherList to the current list.

When writing this method, be sure to use the ArrayListInt methods that we have already implemented. Take a minute to read through the methods we already have before starting this task: can any of them make this task easier? The final method should consist mostly of a simple loop. The goal here is simplicity in terms of code; you do not need to try to optimize how quickly your method runs.

Don't forget to update the number of elements in the list!

Task 2: Concatenating a Singly Linked List

Write a method in LinkedListInt.java called: public void concat(LinkedListInt otherList) that concatenates otherList to the current list.

Your method should not contain any loops: it should make one call to getNode() to get the last node of the current list, and one call to otherList.getNode() (or, alternatively, an access to otherList.head) to get the first node of otherList, after which it should be able to complete the concatenation. Put another way, the goal of this task is to connect existing nodes rather than copying values.

Don't forget to update the number of elements in the list!

Task 3: Concatenating a Doubly Linked List

Write a method in DoublyLinkedListInt.java called: public void concat(DoublyLinkedListInt otherList) that concatenates otherList to the current list.

Your method should not contain any loops: it should make one call to getNode() to get the last node of the current list and one call to otherList.getNode() to get the first node of otherList, after which it should be able to complete the concatenation. It is also OK to use head and tail of each list directly.

Hint: Don't forget to update the tail node! (And don't forget to update the number of elements in the list.)

Task 4: Checking if Palindrome

Write a method in DoublyLinkedListInt.java called: public boolean isPalindrome() that returns true if the list is the same forward and in reverse.

Your method should maintain two nodes: one traversing the list forwards, and the other backwards. At each step, you should check if the value of the nodes is the same.

First Hint: we already have a method, getNode(), that traverses the linked list either forwards or backwards. Use the code there to get started.

Second Hint: this is actually a test of Task 3. If the node traversing in reverse does not work correctly on two lists you concatenated, you probably either forgot to call setPrevious() for a node, or called it incorrectly. For testing, you may want to add some print statements so you know exactly what nodes are being traversed. You should test this method on a list where you have not called concat(), then on a list where you have.

Task 5: Submit

Submit your code to Gradescope (Lab 03) and ensure it passes all autograder tests. Note that the autograder tests call get() and not toString(): this means that the expected output for the autograder and the main method are not quite the same! (The autograder does not have rectangular brackets or commas.) Be sure to upload ArrayListInt.java, LinkedListInt.java, and DoublyLinkedListInt.java each time you commit.

It's time to add, commit and push your file. Enter each of the following commands into your terminal one at a time. (The pdf instructions from Lab00 have more extensive instructions for how to do this.)

git add ArrayListInt.java LinkedListInt.java DoublyLinkedListInt.java
git commit -m "finished with lab 3"
git push

After you commit, log into evolene.cs.williams.edu. Click on your repo, then Lab03, then Lab01.java, and make sure that you can see the modifications you made. If you can see the changes, you're all set! If you finish early, please talk to one of the instructors to make sure everything is in the right place before you leave.