In class, we’ve studied Singly-Linked Lists which are made of nodes that point at subsequent nodes.

INSTRUCTIONS TO CANDIDATES

ANSWER ALL QUESTIONS

Problem 1

Problem 1

In class, we’ve studied Singly-Linked Lists which are made of nodes that point at subsequent nodes.

One of the biggest annoyances with Linked Lists is the difficulty of going backwards through a list

(such as getting the previous node or traversing the list backwards).

An intuitive solution to this inefficiency is the doubly-linked list, which adds pointers to previous

nodes. Doubly-Linked Lists are not very different from Singly-Linked Lists, but are far more

common because they are easier to use.

In this problem, you are to implement a Doubly-Linked List from scratch (you may use the Singly-

Linked List code from class). You will have to create 2 classes (Node and DoublyLinkedList).

The Node class will have the following methods:

_ __init__(value, prev, next)

_ get_prev()

_ get_next()

_ get_value()

_ set_prev(node)

_ set_next(node)

_ set_value(val)

The DoublyLinkedList class must have the following methods:

_ __init__(): Note that there are no extra parameters here

_ add_to_end(val): adds element as last

_ add_to_front(val): adds element to first

_ delete(val): deletes first occurrence of val

_ reverse(): reverses the list

_ compare(lst): check if regular Python list has the same values in the same order as the DLL

_ find(val): return the index(as it would be in a list) of the first occurrence of val

Problem 2

Write a function that will sort a given list using merge sort. You must implement and use the merge

sort algorithm (but may be recursive or iterative). The function will take a list as an input and

return a sorted version of the list (you may assume it will be a list of integers).

 

The method signature must be merge_sort(lst).

One of the biggest annoyances with Linked Lists is the difficulty of going backwards through a list

(such as getting the previous node or traversing the list backwards).

An intuitive solution to this inefficiency is the doubly-linked list, which adds pointers to previous

nodes. Doubly-Linked Lists are not very different from Singly-Linked Lists, but are far more

common because they are easier to use.

In this problem, you are to implement a Doubly-Linked List from scratch (you may use the Singly-

Linked List code from class). You will have to create 2 classes (Node and DoublyLinkedList).

The Node class will have the following methods:

_ __init__(value, prev, next)

_ get_prev()

_ get_next()

_ get_value()

_ set_prev(node)

_ set_next(node)

_ set_value(val)

The DoublyLinkedList class must have the following methods:

_ __init__(): Note that there are no extra parameters here

_ add_to_end(val): adds element as last

_ add_to_front(val): adds element to first

_ delete(val): deletes first occurrence of val

_ reverse(): reverses the list

_ compare(lst): check if regular Python list has the same values in the same order as the DLL

_ find(val): return the index(as it would be in a list) of the first occurrence of val

Problem 2

Write a function that will sort a given list using merge sort. You must implement and use the merge

sort algorithm (but may be recursive or iterative). The function will take a list as an input and

return a sorted version of the list (you may assume it will be a list of integers).

The method signature must be merge_sort(lst).

 

 

Attachments:

Related Questions

. Introgramming & Unix Fall 2018, CRN 44882, Oakland University Homework Assignment 6 - Using Arrays and Functions in C

DescriptionIn this final assignment, the students will demonstrate their ability to apply two ma

. The standard path finding involves finding the (shortest) path from an origin to a destination, typically on a map. This is an

Path finding involves finding a path from A to B. Typically we want the path to have certain properties,such as being the shortest or to avoid going t

. Develop a program to emulate a purchase transaction at a retail store. This program will have two classes, a LineItem class and a Transaction class. The LineItem class will represent an individual

Develop a program to emulate a purchase transaction at a retail store. Thisprogram will have two classes, a LineItem class and a Transaction class. Th

. SeaPort Project series For this set of projects for the course, we wish to simulate some of the aspects of a number of Sea Ports. Here are the classes and their instance variables we wish to define:

1 Project 1 Introduction - the SeaPort Project series For this set of projects for the course, we wish to simulate some of the aspects of a number of

. Project 2 Introduction - the SeaPort Project series For this set of projects for the course, we wish to simulate some of the aspects of a number of Sea Ports. Here are the classes and their instance variables we wish to define:

1 Project 2 Introduction - the SeaPort Project series For this set of projects for the course, we wish to simulate some of the aspects of a number of