Description

Data Structures & Algorithms Assignment

There are three parts in this assignment.

Part 1 Linked Lists and Part 2 Stacks are coding parts, please follow the instruction and submit the coding file. Also, please submit one page writing explanation to explain all the coding process you did.

Part 3 Queues: there is no need for coding, you only need submit one page writing to discuss the question.

1.Linked Lists

You have been provided the code for a singly linked list: singly_linked_list.py. Using this code, perform the following tasks:

·         Create a second type of Node class called DLL_Node

·         Use this node to create a new Python class: DoublyLinkedList.

·         This new class should support all the same operations of insertion, deletion, traversal, and search.

An interesting use‐case of a linked list is to track edits in a "Undo ‐ Redo" interface. Thus far we have really only talked about connecting singular data points in the nodes. The following task will deviate from that:

·         Create a doubly linked list that starts with a single element:[5,3,2,1,4,8]

·         Create a new new node that is a sorted version of the same list.

·         Create another node that holds a reverse of the list.

·         Create another node that holds the data with a new number added to the list: 9.

·         Reverse back to the original state of the list.

Between each step, I'd like you to display the first index in the array that is held in the node, display the last index in the array, and display the highest value in the array. This includes as you reverse back through the array.

2.Stacks

Using a linked structure (doubly, or singly linked list) create a stack structure. From this structure (the stack) and the included text file palindrome.txt, determine which of the words within the file are proper palindromes.

3.Queues

Finally, this last section is not a coding challenge.

A remote printing system serving a large pool of individuals can be very complicated to support. In theory, a simple queue that takes in print requests and dequeue's them once they have been processed would serve all the required operations. However, there are significant problems that arise as far as user requests and other

things. What are some of the issues that you can see with a simple queue that only supports First In First Out operations typical of a queue? (Enqueue, dequeue, peek, etc.) For your submission, please submit a small report of approximately 1 page that discusses the various shortcomings of a queue to support a remote printer system.