Question

04 Prove : Homework - Data Structures

Linked Lists

Outcomes

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

Articulate the strengths and weaknesses of Linked Lists.

Use Linked Lists in Python to solve problems.

Preparation Material

Read the following sections from Wikipedia: Linked Lists:

The Introduction

Advantages

Disadvantages

Basic concepts and nomenclature

The following subsections are sufficient:

Intro

Singly Linked Lists

Doubly Linked Lists

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:

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.

Create a deque of songs for your playlist.

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

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.

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.

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.

Answer 1

The python code is provided below (file name: playlist.py)

from collections import deque

class Song :
    '''
    This class creates instances of song
    '''
    title = ""
    artist = ""

    def prompt(self):
        self.title = input("\nEnter the title of the song: ")
        self.artist = input("Enter the name of the artist: ")

    def display_song_details(self):
        print(self.title, end =" ") 
        print("by ", self.artist)

    # end of class declaration    


def add_song(p):
    '''
    This function adds a song to the playlist
    '''
    newSong = Song()
    newSong.prompt()
    p.append(newSong)
    


def insert_song(p):
    '''
    This functions inserts a new song at the beginning of the playlist so that it plays next
    '''
    newSong = Song()
    newSong.prompt()
    p.appendleft(newSong)

def play_song(p):
    '''
    This functions plays song at the beginning of the playlist
    '''
    if len(list(p)) == 0:
        print("\nThe playlist is currently empty!!!")
        return 0
    song_playing = p.popleft()
    print("\n***********Playing song************\n")
    song_playing.display_song_details()
    return 1


# Driver code
# main code

playlist = deque([])   # deque for creting a playlist

while True:
    print("\n-----------------Menu-------------------\n")
    print("1. Add new song to the end of the playlist.\n")
    print("2. Insert a new song at the beginning of the playlist.\n")
    print("3. Play a song.\n")
    choice = input(">> Select one of the above options(1/2/3): ")

    if choice != '1' and choice != '2' and choice != '3':
        print("\nYou entered the wrong choice!! Select again.")
        continue

    if choice == '1':
        add_song(playlist)

    elif choice == '2':
        insert_song(playlist)

    elif choice == '3':
        o = play_song(playlist)

    leave = input("Do you want to quit (y/n)? ")
    if leave == 'y':
        print("Bye!")
        break

# End of program

Steps to execute the program:

1. Move to the source code directory in a command prompt or terminal.

2. Enter the following command to execute the code:

> python3 playlist.py

----- That's it!