logo Use CA10RAM to get 10%* Discount.
Order Nowlogo
(5/5)

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

 

 

(5/5)
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

Ask This Question To Be Solved By Our ExpertsGet A+ Grade Solution Guaranteed

expert
Um e HaniScience

515 Answers

Hire Me
expert
Muhammad Ali HaiderFinance

819 Answers

Hire Me
expert
Husnain SaeedComputer science

691 Answers

Hire Me
expert
Atharva PatilComputer science

628 Answers

Hire Me

Get Free Quote!

271 Experts Online