OO Programming and Data Structures | CS 241

04 Prove : Homework - Data Structures

Linked Lists

Outcomes

At the end of this study, successful students will be able to:

1. Articulate the strengths and weaknesses of Linked Lists.

2. Use Linked Lists in Python to solve problems.

Preparation Material

Read the following sections from Wikipedia: Linked Lists:

1. The Introduction

2. Advantages

3. Disadvantages

4. Basic concepts and nomenclature

   The following subsections are sufficient:

   • Intro

   • Singly Linked Lists

   • Doubly Linked Lists

5. Tradeoffs

   The following subsections are sufficient:

   • Linked Lists vs. Dynamic Arrays

Data Structures for the Common Person

After going over the technical details of linked lists above, please watch the following short video, containing a non-computing example:

Using Linked Lists in Python

Many languages have a LinkedList library that provides all of this behavior for you. Python does not specifically have a "LinkedList" collection. It does, however, have a deque (Double-ended queue, pronounced "deck"), which is in fact implemented as a doubly-linked list (see: StackOverflow).

The Deque is a generalization of stacks and queues (which we will learn about in future weeks), but provides all the functionality we would expect from a LinkedList, with O(1) insertion and removal from the beginning and end of the list, and O(n) retrieval of an item at a specific index. See the Python documentation for a list of available methods, but in short:

• append(x) - Adds x to the end of the list

• appendleft(x) - Adds x to the beginning of the list

• insert(i, x) - Inserts x at index i

• pop() - Removes and returns the last item in the list

• popLeft() - Removes and returns the first item in the list

In addition, you can iterate over a deque, using a for loop, just like a list:

from collections import deque

cars = deque()
cars.append("Ford")
cars.append("Mazda")
cars.append("Dodge")

for car in cars:
    print(car)

And, you technically can use the index notation to access and object (e.g., print(cars[2]), but remember, this is an O(n) operation, so if we are wanting to do this much, a linked list may not be the right choice.

Homework Assignment

Use a linked list (i.e., a Python deque) to keep track of a playlist of songs. Your playlist should have the functionality to add songs to the end of the list, insert a new one at the first of the list (so that it is played next), and then to play a song (which removes it from the list).

Instructions

Follow these steps to help guide you through the assignment:

1. Create a Song class that has member variables for a title and an artist. It should have a prompt function that asks the user for the title and artist, and a display function that displays the title and the artist to the screen.

2. Create a deque of songs for your playlist.

3. Set up a main loop that asks the user for one of the following options:

• Add new song to the end of the playlist.

• Insert a new song at the beginning of the playlist (so it will play next).

• Play a song (this should remove it from the playlist).

4. Implement each of the above actions. For the ones that add a new song, it should prompt the user for the values, and then add the song to the play list.

5. When the user selects the option to play a song, it should be removed from the list. Then, display a message to the user, "Playing song:", followed by the title and the artist of the song that was just removed from the front of the playlist.

6. If the user attempts to play a song and the playlist is empty, they should receive a message that informs them the playlist is empty, and then they can make another selection. (A Python error message should not occur and be displayed.)

Example output

Options:
1. Add a new song to the end of the playlist
2. Insert a new song to the beginning of the playlist
3. Play the next song
4. Quit
Enter selection: 3

The playlist is currently empty.

Options:
1. Add a new song to the end of the playlist
2. Insert a new song to the beginning of the playlist
3. Play the next song
4. Quit
Enter selection: 1

Enter the title: Let it Be
Enter the artist: The Beatles

Options:
1. Add a new song to the end of the playlist
2. Insert a new song to the beginning of the playlist
3. Play the next song
4. Quit
Enter selection: 2

Enter the title: The Sound of Silence
Enter the artist: Simon and Garfunkel

Options:
1. Add a new song to the end of the playlist
2. Insert a new song to the beginning of the playlist
3. Play the next song
4. Quit
Enter selection: 3

Playing song:
The Sound of Silence by Simon and Garfunkel

Options:
1. Add a new song to the end of the playlist
2. Insert a new song to the beginning of the playlist
3. Play the next song
4. Quit
Enter selection: 3

Playing song:
Let it Be by the Beatles

Options:
1. Add a new song to the end of the playlist
2. Insert a new song to the beginning of the playlist
3. Play the next song
4. Quit
Enter selection: 3

The playlist is currently empty.

Options:
1. Add a new song to the end of the playlist
2. Insert a new song to the beginning of the playlist
3. Play the next song
4. Quit
Enter selection: 4

Goodbye

Testing your Playlist program

To help keep your focus squarely on the data structure involved, and not on matching a particular testBed output, an automated grading script is not provided. Instead, test your own code by adding different songs to the beginning and end of the playlist, and playing them. Ensuring that everything works as you would expect.

Submission

When you have a good understanding of this data structure and have completed the programming project, take the accompanying I-Learn Quiz. It has questions about how the data structure works, and also, has places for your to report on the parts of the programming assignment that you completed.