patternjavaMinor
Java Doubly Linked List Implementation
Viewed 0 times
implementationjavadoublylistlinked
Problem
I recently submitted an implementation of a singly linked list and tried to apply some of the suggestions on this implementation. I decided not to implement the List interface as I only wanted to practice what I believed to be the most important methods. I'm wondering how I could tidy this up some more and improve upon it.
Singly Linked List: Java Singly Linked List Implementation
DoublyLinkedList.java
```
public class DoublyLinkedList {
private class Node {
private T data;
Node next, prev;
public Node() {
}
public Node(T data) {
this.data = data;
}
}
private Node head, last;
private int size;
public DoublyLinkedList() {
this.size = 0;
}
public void addToBeginning(T data) {
Node temp = new Node(data);
if (head == null) {
head = temp;
last = head;
} else {
temp.next = head;
head.prev = temp;
head = temp;
}
size++;
}
public void add(T data) {
Node temp = new Node(data);
if (head == null) {
head = temp;
last = head;
} else {
last.next = temp;
temp.prev = last;
last = temp;
}
size++;
}
public void add(T data, int index) {
Node temp = new Node(data);
if (index size) {
throw new IndexOutOfBoundsException();
} else if (index == 0) {
addToBeginning(data);
} else if (index == size) {
add(data);
} else {
Node current = head;
for (int i = 0; i = size) {
throw new IndexOutOfBoundsException();
} else {
Node current = head;
for (int i = 0; i = size) {
throw new IndexOutOfBoundsException();
} else if (index == 0) {
head = head.next;
head.prev = null;
size--;
Singly Linked List: Java Singly Linked List Implementation
DoublyLinkedList.java
```
public class DoublyLinkedList {
private class Node {
private T data;
Node next, prev;
public Node() {
}
public Node(T data) {
this.data = data;
}
}
private Node head, last;
private int size;
public DoublyLinkedList() {
this.size = 0;
}
public void addToBeginning(T data) {
Node temp = new Node(data);
if (head == null) {
head = temp;
last = head;
} else {
temp.next = head;
head.prev = temp;
head = temp;
}
size++;
}
public void add(T data) {
Node temp = new Node(data);
if (head == null) {
head = temp;
last = head;
} else {
last.next = temp;
temp.prev = last;
last = temp;
}
size++;
}
public void add(T data, int index) {
Node temp = new Node(data);
if (index size) {
throw new IndexOutOfBoundsException();
} else if (index == 0) {
addToBeginning(data);
} else if (index == size) {
add(data);
} else {
Node current = head;
for (int i = 0; i = size) {
throw new IndexOutOfBoundsException();
} else {
Node current = head;
for (int i = 0; i = size) {
throw new IndexOutOfBoundsException();
} else if (index == 0) {
head = head.next;
head.prev = null;
size--;
Solution
There is one thing missing: iteration.
There is no way for the user code to get all items stored in the list without doing
Building the ListIterator without remove support is simple enough you just need to have it keep a reference to the current node.
There is no way for the user code to get all items stored in the list without doing
get(int) for each item which will result in O(n^2) time complexity.Building the ListIterator without remove support is simple enough you just need to have it keep a reference to the current node.
Context
StackExchange Code Review Q#122535, answer score: 3
Revisions (0)
No revisions yet.