In the java examples we’ve shown so far, we’ve stored primitive variables of typ
ID: 3796040 • Letter: I
Question
In the java examples we’ve shown so far, we’ve stored primitive variables of type int in our data structures. Storing such variables simplifies the program examples, but it’s not representative of how you use data storage structures in the real world. Usually, the data items (records) you want to store are combinations of many fields. For a personnel record, you would store last name, first name, age, Social Security number, and so forth. For a stamp collection, you would store the name of the country that issued the stamp, its catalog number, condition, current value, and so on. In your homework, you need to show how objects, rather than variables of primitive types, can be stored. This time you need to use a linked list.
The provided classes are: a reference data type, and the Link class for singly linked list and doubly linked list. Notice that the Link class does not have a int or double as its data element. Instead, now it contains a reference variable field.
Part A. Singly Linked List. Start by creating a singly linked list to use as your data structure for this task. In addition to the first(head)field that we practiced with in class, you will also maintain a last(tail)field. Include the below standard linked list features/methods in your class
Constructor
isEmpty()
insertFirst()
insertLast()
deleteFirst()
displayList()
For each method, be sure to test your work by adding test code to a main method in a SingleListedListTestApp class.
Part B. Doubly Linked List. Create a second program that achieves the same goal as your first one, but uses a doubly-linked list rather than a singly-linked list. You will need to first create a Link class, that will have an extra field (called previous) for the backward reference. Link is the class you will use to build your doubly linked list.
For this program, after creating the fields and the constructor method, you need to add the following methods:
constructor
isEmpty()
insertFirst()
insertLast()
deleteFirst()
deleteLast()
insertAfter()
deleteKey()
displayForward()
displayBackward()
Warning: you might be tempted to try copying and pasting from the methods you wrote above, then modifying the code. However, these methods in a doubly-linked list class are significantly different, and more streamlined. You should write them from scratch rather than confuse things by trying to reuse old code.
For each method, be sure to test your work by adding test code to a main method in a doublyListedListTestApp class.
Submission- you need to submit the following java files
Reference data type
Data member
Constructor(s)
getMethod(s)
setMethod(s)
SinglyLinked.java
Link class for singly linked list
Singly linked list class
Main method to test singly linked list class
DoublyLined.java
Link class for doubly li
In the java examples we’ve shown so far, we’ve stored primitive variables of type int in our data structures. Storing such variables simplifies the program examples, but it’s not representative of how you use data storage structures in the real world. Usually, the data items (records) you want to store are combinations of many fields. For a personnel record, you would store last name, first name, age, Social Security number, and so forth. For a stamp collection, you would store the name of the country that issued the stamp, its catalog number, condition, current value, and so on. In your homework, you need to show how objects, rather than variables of primitive types, can be stored. This time you need to use a linked list.
The provided classes are: a reference data type, and the Link class for singly linked list and doubly linked list. Notice that the Link class does not have a int or double as its data element. Instead, now it contains a reference variable field.
Part A. Singly Linked List. Start by creating a singly linked list to use as your data structure for this task. In addition to the first(head)field that we practiced with in class, you will also maintain a last(tail)field. Include the below standard linked list features/methods in your class
Constructor
isEmpty()
insertFirst()
insertLast()
deleteFirst()
displayList()
For each method, be sure to test your work by adding test code to a main method in a SingleListedListTestApp class.
Part B. Doubly Linked List. Create a second program that achieves the same goal as your first one, but uses a doubly-linked list rather than a singly-linked list. You will need to first create a Link class, that will have an extra field (called previous) for the backward reference. Link is the class you will use to build your doubly linked list.
For this program, after creating the fields and the constructor method, you need to add the following methods:
constructor
isEmpty()
insertFirst()
insertLast()
deleteFirst()
deleteLast()
insertAfter()
deleteKey()
displayForward()
displayBackward()
Warning: you might be tempted to try copying and pasting from the methods you wrote above, then modifying the code. However, these methods in a doubly-linked list class are significantly different, and more streamlined. You should write them from scratch rather than confuse things by trying to reuse old code.
For each method, be sure to test your work by adding test code to a main method in a doublyListedListTestApp class.
Submission- you need to submit the following java files
Reference data type
Data member
Constructor(s)
getMethod(s)
setMethod(s)
SinglyLinked.java
Link class for singly linked list
Singly linked list class
Main method to test singly linked list class
DoublyLined.java
Link class for doubly linked list
Doubly linked list class
Main method to test doubly linked list class
nked list
Doubly linked list class
Main method to test doubly linked list class
Explanation / Answer
===================================SingleLinkedList=====================================
class Test{
public static void main(String[] args){
SingleLinkedList list = new SingleLinkedList();
list.insertFirst(new ListNode(new Student("loknath")));
list.insertLast((new ListNode(new Student("rahul"))));
list.insertFirst(new ListNode(new Student("ritesh")));
list.insertFirst(new ListNode(new Student("ravi")));
list.insertFirst(new ListNode(new Student("rajas")));
System.out.println("list :"+list);
list.deleteFirst();
System.out.println("after delete first, list :"+list);
list.deleteLast();
System.out.println("after delete last, list :"+list);
}
}
class SingleLinkedList {
ListNode head;
private int length = 0;
public SingleLinkedList() {
length = 0;
}
public void insertFirst(ListNode node) {
node.setNext(head);
head = node;
length ++;
}
public void insertLast(ListNode node) {
if (head == null)
head = node;
else {
ListNode p, q;
for(p = head; (q = p.getNext()) != null; p = q);
p.setNext(node);
}
length ++;
}
public void insertAt(Student data, int position) {
if (position < 0) {
position = 0;
}
if (position > length) {
position = length;
}
if (head == null) {
head = new ListNode(data);
}
else if (position == 0) {
ListNode temp = new ListNode(data);
temp.next = head;
head = temp;
}
else {
ListNode temp = head;
for (int i=1; i<position; i+=1) {
temp = temp.getNext();
}
ListNode newNode = new ListNode(data);
newNode.next = temp.next;
temp.setNext(newNode);
}
length += 1;
}
public ListNode deleteFirst() {
ListNode node = head;
if (node != null) {
head = node.getNext();
node.setNext(null);
}
return node;
}
public ListNode deleteLast() {
if (head == null)
return null;
ListNode p = head, q = null, next = head.getNext();
if (next == null) {
head = null;
length-=1;
return p;
}
while((next = p.getNext()) != null) {
q = p;
p = next;
}
q.setNext(null);
length-=1;
return p;
}
public String toString() {
String result = "[";
if (head == null) {
return result+"]";
}
result = result + head.getData();
ListNode temp = head.getNext();
while (temp != null) {
result = result + "," + temp.getData();
temp = temp.getNext();
}
return result + "]";
}
public int length() {
return length;
}
public boolean isEmpty(){
return length==0;
}
}
class ListNode{
public ListNode next;
public Student data;
public ListNode(){
next = null;
data = null;
}
public ListNode (Student data){
next = null;
this.data = data;
}
public ListNode getNext(){
return next;
}
public void setNext (ListNode node){
next = node;
}
public Student getData(){
return data;
}
public void setdata (Student elem){
data = elem;
}
}
class Student{
private int id;
private String name;
private String cource;
public Student(){
}
public Student(String name){
this.name = name;
}
public int getId() {
return id;
}
public void setId(int id) {
this.id = id;
}
public String getName() {
return name;
}
public void setName(String name) {
this.name = name;
}
public String getCource() {
return cource;
}
public void setCource(String cource) {
this.cource = cource;
}
public String toString(){
return name;
}
}
===================================DoublyLinkedList=====================================
class Test{
public static void main(String[] args){
DoublyLinkedList list = new DoublyLinkedList();
list.insertFirst(1);
list.insertLast(10);
list.insertFirst(2);
list.insertFirst(3);
list.insertFirst(4);
System.out.println("list :"+list);
list.deleteFirst();
System.out.println("after delete first, list :"+list);
list.deleteLast();
System.out.println("after delete last, list :"+list);
}
}
class DoublyLinkedList{
private DLLNode head;
private DLLNode tail;
private int length;
public DoublyLinkedList() {
head = new DLLNode(Integer.MIN_VALUE,null,null);
tail = new DLLNode(Integer.MIN_VALUE, head, null);
head.setNext(tail);
length = 0;
}
public int length() {
return length;
}
public void insertFirst(int newValue) {
DLLNode newNode = new DLLNode(newValue,null,head.getNext());
newNode.getNext().setPrev(newNode);
head.setNext(newNode);
length += 1;
}
public void insertAfter(int data, int position) {
if (position < 0) {
position = 0;
}
if (position > length) {
position = length;
}
if (head == null) {
head = new DLLNode(data);
tail = head;
}
else if (position == 0) {
DLLNode temp = new DLLNode(data);
temp.next = head;
head = temp;
}
else {
DLLNode temp = head;
for (int i=1; i<position; i+=1) {
temp = temp.getNext();
}
DLLNode newNode = new DLLNode(data);
newNode.next = temp.next;
newNode.prev = temp;
newNode.next.prev = newNode;
temp.next = newNode;
}
length += 1;
}
public void insertLast(int newValue) {
DLLNode newNode = new DLLNode(newValue,tail.getPrev(),tail);
newNode.getPrev().setNext(newNode);
tail.setPrev(newNode);
length += 1;
}
public void delete(int position) {
// fix position
if (position < 0) {
position = 0;
}
if (position >= length) {
position = length-1;
}
if (head == null)
return;
if (position == 0) {
head = head.getNext();
if (head == null)
tail = null;
}
else {
DLLNode temp = head;
for (int i=1; i<position; i+=1) {
temp = temp.getNext();
}
temp.getNext().setPrev(temp.getPrev());
temp.getPrev().setNext(temp.getNext());
}
length -= 1;
}
public void deleteKey(DLLNode node) {
if (head == null)
return;
if (node.equals(head)) {
head = head.getNext();
if (head == null)
tail = null;
return;
}
DLLNode p = head;
while(p != null) {
if (node.equals(p)) {
p.prev.next = p.next;
p.next.prev = p.prev;
return;
}
}
}
public int deleteFirst() {
if (length == 0)
return Integer.MIN_VALUE;
DLLNode save = head.getNext();
head.setNext(save.getNext());
save.getNext().setPrev(head);
length -= 1;
return save.getData();
}
public int deleteLast() {
if (length == 0)
return Integer.MIN_VALUE;
DLLNode save = tail.getPrev();
tail.setPrev(save.getPrev());
save.getPrev().setNext(tail);
length -= 1;
return save.getData();
}
public String toString() {
String result = "[]";
if (length == 0)
return result;
result = "[" + head.getNext().getData();
DLLNode temp = head.getNext().getNext();
while (temp != tail) {
result += "," + temp.getData();
temp = temp.getNext();
}
return result + "]";
}
}
class DLLNode {
public int data;
public DLLNode prev;
public DLLNode next;
public DLLNode(int data) {
this.data = data;
prev = null;
next = null;
}
public DLLNode(int data, DLLNode prev, DLLNode next) {
this.data = data;
this.prev = prev;
this.next = next;
}
public int getData() {
return data;
}
public void setData(int data) {
this.data = data;
}
public DLLNode getPrev() {
return prev;
}
public DLLNode getNext() {
return next;
}
public void setPrev(DLLNode where) {
prev = where;
}
public void setNext(DLLNode where) {
next = where;
}
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.