Question: Modify this student map code to make the linked list into a doubly-linked list. To do this: Each node should track the previous node. Youll
Modify this student map code to make the linked list into a doubly-linked list. To do this:
- Each node should track the previous node. Youll need to update other sections of code to update the previous node correctly.
- In this section and others, think about four cases: when the list starts or becomes empty, if the node youre adding or removing is at the beginning, if the node is at the end, and if the node is in the middle (essentially, anywhere but the beginning or end)
- The linked list should track the tail (or last)the last node in the list
- Make sure that all references (head, tail, as well as each nodes next and previous) are correct after nodes are added and removed.
- Be particularly thoughtful about adding a node when the list is empty, or removing a node to make it empty, as those tend to need extra thought to set up the references correctly.
- Dont just use the existing main method to test your code, since it wont use and test out all the methods written here and in various situations. Youll instead need to write some test code to make sure theyre working.
- One good test is to print out the list forwards from the head and then backwards from the taildoing that after calling a method can help you spot if theres a problem with a next or previous link, or with updating the head or tail.
- Modify the addLast method so that it efficiently adds a new students to the end of the listit should be O(1).
- Modify removeLast so that it efficiently removes a student from the end of the listit should be O(1).
public class LinkedList {
private Node head;
public LinkedList() {
head = null;
}
public void addFirst(int key, Student value) {
Node addNode = new Node(key, value);
addNode.setNext(head);
head = addNode;
}
public void addLast(int key, Student value) {
// If list is empty
if (head == null) {
head = new Node(key, value);
return;
}
// If list is not empty, find the last item, add new node after that
Node last = head;
while (last.getNext() != null) {
last = last.getNext();
}
Node addNode = new Node(key, value);
last.setNext(addNode);
}
public void removeLast() {
if (head == null) {
return;
}
// If list is not empty, find the last item, add new node after that
Node last = head;
Node nextToLast = null;
while (last.getNext() != null) {
nextToLast = last;
last = last.getNext();
}
if (nextToLast == null) {
head = null;
} else {
nextToLast.setNext(null);
}
}
public Student getById(int key) {
Node current = head;
while (current != null) {
if (current.getKey() == key) {
return current.getValue();
}
current = current.getNext();
}
return null;
}
public void removeFirst() {
if (head == null) {
return;
}
head = head.getNext();
}
public int count() {
int count = 0;
Node currentNode = head;
while (currentNode != null) {
count++;
currentNode = currentNode.getNext();
}
return count;
}
public void remove(int key) {
Node currentNode = head;
Node prevNode = null;
// Walk through list
while (currentNode != null) {
// If currentNode is one we're searching for
if (currentNode.getKey() == key) {
if (currentNode == head) {
// Node to be removed is first node, update head to refer to the next node
head = currentNode.getNext();
} else {
// Otherwise there is a previous node, update previous so its next skips the node we're removing
prevNode.setNext(currentNode.getNext());
}
// We removed matching node, can return
return;
}
// Haven't found the student we're looking for, walk to next node
prevNode = currentNode;
currentNode = currentNode.getNext();
}
}
}
public class Node {
private Node next;
private int key;
private Student value;
public Node(int key, Student value) {
this.key = key;
this.value = value;
this.next = null;
}
public Node getNext() {
return next;
}
public void setNext(Node next) {
this.next = next;
}
public Student getValue() {
return value;
}
public void setValue(Student value) {
this.value = value;
}
public int getKey() {
return key;
}
public void setKey(int key) {
this.key = key;
}
}
public class Student {
private String name;
private String major;
private int level;
public Student(String name, String major, int level) {
this.name = name;
this.major = major;
this.level = level;
}
public String getName() {
return name;
}
public void setName(String name) {
this.name = name;
}
public String getMajor() {
return major;
}
public void setMajor(String major) {
this.major = major;
}
public int getLevel() {
return level;
}
public void setLevel(int level) {
this.level = level;
}
}
public class StudentMapMain {
public static void main(String[] args) {
LinkedList studentMap = new LinkedList();
studentMap.addLast(40, new Student("Dwayne Johnson", "Culinary Arts", 4));
studentMap.addLast(3, new Student("Tom Holland", "Biology", 3));
Student test = studentMap.getById(40);
System.out.println(test.getName());
}
}
Step by Step Solution
There are 3 Steps involved in it
Get step-by-step solutions from verified subject matter experts
Study Help