# CSE1030 Lab 08

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):

• copy constructor
• `addAll` and its private recursive helper method
• `zipper`

`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
```