HiveBrain v1.2.0
Get Started
← Back to all entries
patternjavaMinor

Java Doubly Linked List Implementation

Submitted by: @import:stackexchange-codereview··
0
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--;

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