CSE1030 Lab 08

Linked lists

Week of Mar 24
Due: before Fri Apr 4 11:59PM

Introduction

The linked list is one of the simplest and most common data structures encountered in computer science. A linked list is a sequence of nodes where each node stores a data value (an element of the list) and a reference to the next node in the sequence. The first element in a linked list is stored in a node called the head.

A linked list is a recursive data structure in that each node of the list can be thought of as being the head node of a shorter list. The recursive structure of the linked list leads naturally to recursive implementations of the list methods. Recursive implementations of many linked list methods can be found here.

This lab provides you with an incomplete implementation of a singly linked list and asks you to complete the implementation of a few methods.

Question: Complete the implementation of some linked list methods

Here are some resources for this lab:

The starter code contains a partial implementation of a singly linked list using nodes. Two of the given methods are implemented as recursive methods: add and get. Two of the given methods are implemented as iterative methods: set and toString. Finally, two of the given methods operate on the head node of the list: addFirst and removeFirst. You should study these methods to see the differences in the recursive and iterative implementation.

You must complete the implementation of the following three constructors and methods (partially given at the end of the starter code):

addAll(CharLinkedList other) should be implemented using recursion; make sure that you make a copy other and pass the copy to the recursive helper method, otherwise you might end up with two linked lists that share nodes! You can choose the implement the constructor and zipper using either recursion or iteration; if you use recursion, you will need to create private methods that perform the actual recursion.

Submit your work

submit 1030 L8 CharLinkedList.java