I'm a C++ programmer learning Java in preparation for an OOP class this fall. That being said, Java is fairly new to me so I'd love to hear feedback on how to improve this code.
A few notes:
- Code works as expected and is ported from my C++ equivalent code I wrote some time ago.
- Not all operations that should be implemented have been implemented yet (Search, Remove, etc). Of course, that would be more fitting for BSTs or other data structures for efficiency's sake.
node.java
public class node<T> {
public node() {
this.setNext(null);
this.setPrev(null);
}
public node(T k) {
this.setNext(null);
this.setPrev(null);
this.setKey(k);
}
public node<T> getNext() {
return next;
}
public void setNext(node<T> next) {
this.next = next;
}
public node<T> getPrev() {
return prev;
}
public void setPrev(node<T> prev) {
this.prev = prev;
}
public T getKey() {
return key;
}
public void setKey(T key) {
this.key = key;
}
private node<T> next;
private node<T> prev;
private T key;
}
List.java
public class list<T> {
public list() {
head = null;
}
/* Description: Deletes the head node from the linked list and returns the head node's key.
* Running Time: O(1)
* Precondition: Linked list must not be null
* Postcondition: The head node is deleted and its key is returned. */
public T pop() {
if(isEmpty()) return null;
T k = head.getKey();
if(head == head.getNext()) {
head = null;
}
else {
node<T> f = head, b = head.getPrev();
b.setNext(f.getNext());
head = head.getNext();
head.setPrev(b);
}
return k;
}
/* Description: Deletes the tail node from the linked list and returns its node's key.
* Running Time: O(1)
* Precondition: Linked list must not be null
* Postcondition: The tail node is deleted and its key is returned. */
public T pop_back() {
if(isEmpty()) return null;
T k = head.getPrev().getKey();
if(head == head.getPrev()) {
head = null;
}
else {
node<T> b = head.getPrev();
b.getPrev().setNext(head);
head.setPrev(b.getPrev());
}
return k;
}
public void print() {
node<T> p = head;
if(isEmpty()) return;
else if(p == p.getNext()) {
System.out.println(p.getKey());
}
else {
do {
System.out.println(p.getKey());
p = p.getNext();
} while (p != head);
}
}
/* Description: Allocates a new node x and inserts the node into the back of the linked list.
* Running Time: O(1)
* Precondition: Linked list must be instantiated.
* Postcondition: A node x with the key passed in through k is inserted into the back of the linked list. */
public void push_back(T k) {
node<T> x = new node<T>(k);
push_back(x);
}
/* Description: Inserts node x into the back of the linked list.
* Running Time: O(1)
* Precondition: Node x must be allocated
* Postcondition: A node x is inserted into the back of the linked list.*/
private void push_back(node<T> x) {
if(isEmpty()) {
head = x;
head.setNext(head);
head.setPrev(head);
}
else {
node<T> p = head.getPrev();
p.setNext(x);
x.setPrev(p);
x.setNext(head);
head.setPrev(x);
}
}
/* Description: Allocates a new node x and inserts the node into the front of the linked list.
* Running Time: O(1)
* Precondition: Linked list must be instantiated.
* Postcondition: A node x with the key passed in through k is inserted into the front of the linked list. */
public void push_front(T k) {
node<T> x = new node<T>(k);
push_front(x);
}
/* Description: Inserts node x into the front of the linked list.
* Running Time: O(1)
* Precondition: Node x must be allocated
* Postcondition: A node x is inserted into the front of the linked list.*/
private void push_front(node<T> x) {
if(isEmpty()) {
head = x;
head.setNext(head);
head.setPrev(head);
}
else {
node<T> b = head.getPrev();
b.setNext(x);
head.setPrev(x);
x.setNext(head);
x.setPrev(b);
head = x;
}
}
public T top() {
if(isEmpty()) return null;
return head.getKey();
}
public boolean isEmpty() {
return (head == null);
}
private node<T> head;
}