I’ve written a quick implementation of a doubly-linked list in java, looking for critiques and advice on approach, efficiency, and style. From my understanding, the primary advantage of using a doubly-linked list over a singly-linked list is not requiring a pointer to previous node when performing removals; are there any other real benefits? Also, would my implementation be considered a circular list, since it maintains a pointer to the tail element of the list?
DoublyLinkedList:
public class DoublyLinkedList<T> { private ListNode<T> head; private ListNode<T> tail; private int size; public DoublyLinkedList() { this.head = new ListNode(); this.size = 0; } /** * Inserts data element at the front of the list. * @param data data to insert. */ public void insertFront(T data) { ListNode<T> newNode = new ListNode.ListNodeBuilder().data(data).build(); if(isEmpty()) { this.head = newNode; this.tail = this.head; } else { this.head.setPrev(newNode); newNode.setNext(this.head); this.head = newNode; } this.size++; } /** * Inserts data element at the end of the list. * @param data data to insert. */ public void insertEnd(T data) { ListNode<T> newNode = new ListNode.ListNodeBuilder().data(data).build(); if(isEmpty()) { this.head = newNode; this.tail = this.head; } else { ListNode<T> temp = this.tail; newNode.setPrev(temp); temp.setNext(newNode); this.tail = temp.getNext(); } this.size++; } /** * Inserts element at a specific index within the list. * @param index position at which to insert. * @param data element to insert. */ public void insertAt(int index, T data) { ListNode<T> newNode = new ListNode.ListNodeBuilder().data(data).build(); if(isEmpty()) { this.head = newNode; this.tail = this.head; } else if(index == 0) { insertFront(data); } else { ListNode<T> temp = this.head; for(int i = 1; i < index; i++) { temp = temp.getNext(); } newNode.setPrev(temp); newNode.setNext(temp.getNext()); temp.setNext(newNode); } this.size++; } /** * Removes head element of list. */ public void removeFront() { if(!isEmpty()) { if(this.head.getNext() != null) { this.head = this.head.getNext(); } else { this.head = null; this.tail = null; } this.size--; } } /** * Removes tail element of list. */ public void removeEnd() { if(!isEmpty()) { if(this.tail.getPrev() != null) { this.tail = this.tail.getPrev(); } else { this.tail = null; this.head = null; } this.size--; } } /** * Removes element at a specific index from list. * @param index position at which to remove element. */ public void removeAt(int index) { if(!isEmpty()) { if(index == 0) { removeFront(); } else { ListNode<T> temp = this.head; for(int i = 0; i < index; i++) { temp = temp.getNext(); } temp.getPrev().setNext(temp.getNext()); temp = temp.getPrev(); } this.size--; } } /** * Returns the head element of the list. * @return the element at the head of the list */ public T getElementAtFront() { return (!isEmpty()) ? this.head.getData() : null; } /** * Returns the tail element of the list. * @return the tail element of the list. */ public T getElementAtEnd() { return (!isEmpty()) ? this.tail.getData() : null; } /** * Returns the element at a specific index within the list. * @param index position at which to search for / return element. * @return the element located at the given index. */ public T getElementAt(int index) { if(!isEmpty()) { if(index == 0) { return getElementAtFront(); } else if(index == this.size - 1) { return getElementAtEnd(); } else { ListNode<T> temp = this.head; for(int i = 0; i < index; i++) { temp = temp.getNext(); } return temp.getData(); } } return null; } /** * Finds the index of a specific element within the list, if it exists. * @param data the element to search for within the list. * @return the index of the queried element, -1 if element does not exist within list. */ public int find(T data) { if(!isEmpty()) { ListNode<T> temp = this.head; int i = 0; while (temp != null) { if (temp.getData().equals(data)) { return i; } temp = temp.getNext(); i++; } } return -1; } /** * Returns contents of list in an array format. * @param clazz class of underlying generic type. * @return the array containing all list elements. */ public T[] toArray(Class<T> clazz) { T[] arr = (T[])Array.newInstance(clazz, this.size); ListNode<T> temp = this.head; for(int i = 0; i < arr.length; i++) { arr[i] = temp.getData(); temp = temp.getNext(); } return arr; } /** * Determines whether the underlying list structure is empty or not. * @return true if list is empty, false if otherwise. */ public boolean isEmpty() { return this.size == 0; } /** * Returns the current size of the list. * @return integer representing current list size. */ public int getSize() { return this.size; } }
ListNode:
public class ListNode<T> { private T data; private ListNode<T> next; private ListNode<T> prev; public ListNode() {} public ListNode(T data) { this.data = data; } private ListNode(ListNodeBuilder<T> builder) { this.data = builder.data; this.next = builder.next; this.prev = builder.prev; } public T getData() { return data; } public void setData(T data) { this.data = data; } public ListNode<T> getNext() { return next; } public void setNext(ListNode<T> next) { this.next = next; } public ListNode<T> getPrev() { return prev; } public void setPrev(ListNode<T> prev) { this.prev = prev; } public static class ListNodeBuilder<T> { private T data; private ListNode<T> next; private ListNode<T> prev; public ListNode<T> build() { return new ListNode<>(this); } public ListNodeBuilder<T> data(T data) { this.data = data; return this; } public ListNodeBuilder<T> next(ListNode<T> next) { this.next = next; return this; } public ListNodeBuilder<T> prev(ListNode<T> prev) { this.prev = prev; return this; } } }