03. Implementing a Linked List

Parameters

Our linked list should have a head and tail, which point to the first and last nodes. Additionally, a integer value that contains how many nodes are in our list (listSize) is useful for our purposes.

Node Inner Class

To implement a linked list, we need a node class that holds an element and a pointer to the next node. We create this class within the LinkedList object.

Adding / Insertion

There are three methods for adding: addToHead(), addToTail(), and addAfterIndex().

To add, we must create a new node. Then we traverse the linked list until we get to the targetNode, which is where we are to insert our new node after.

Then we have to set our new node's next to the targetNode's next. Then our targetNode's next must be set to our newNode. Don't forget to increment the listSize!

Node newNode = new Node<>(data);
 
// Traverse to the Node that we want to insert after
Node targetNode = this.head;
 
for (int i = 1; i < index; i++) {
  targetNode = targetNode.getNext();
}
 
newNode.setNext(targetNode.getNext());
targetNode.setNext(newNode);
this.listSize++;

Removing / Deleting

We have three similar methods as in adding: removeHead(), removeTail(), and removeAtIndex().

Additionally, when removing from a linked list, it is customary to return the data being removed.

We first load our previousNode variable with the head of the linked list, then traverse until we get to the user's desired index. Then we place that node's data into the nodeData variable, which we'll use to return. To do the actual deleting, we link the previousNode to the next-next node. Java's garbage collector can take care of the rest, but if you're using C, you must deallocate the memory.

Node previousNode = this.head;
 
// Reaches to the previous of the node we want to remove
for (int i = 1; i < index - 1; i++) {
  previousNode = previousNode.getNext();
}
E nodeData = previousNode.getNext().getData();
previousNode.setNext(previousNode.getNext().getNext());
listSize--;
return nodeData; 

Full code

Here's the entire code. There are some intracacies of adding or removing from the head and tail that you may want to review.

/** 
 * A <code>LinkedList</code> implementation that uses the Node class.
 * 
 * @author Code Snipcademy 
 * @version 1.0.0 Dec 07, 2015
 */
public class LinkedList<E> {
 
  protected Node<E> head;      // First node
  protected Node<E> tail;      // Last node
  protected int listSize;      // Size of  LinkedList
 
  /**
   * Default constructor for LinkedList.
   * 
   * Points head and tail to null.
   * ListSize is initially zero.
   */
  public LinkedList() {
    this.head = null;
    this.tail = null;
    this.listSize = 0;
  }
 
  /**
   * Output LinkedList in String format.
   */
  public String toString() {
    Node<E> currentNode = this.head;
    StringBuilder output = new StringBuilder();
    while (currentNode != null) { 
      output.append("[");
      output.append(currentNode.getData());
      output.append("]");
      currentNode = currentNode.getNext();
    }
    return output.toString();
  }
 
  /**
   * Return the amount of Nodes in our LinkedList.
   */
  public int size() { 
    return this.listSize; 
  }
  
  /**
   * Return true if LinkedList is empty.
   *
   * @return true if no Nodes in LinkedList.
   */
  private boolean isEmpty() { 
    return this.size() == 0; 
  }
 
  /**
   * Clears the list - all elements are to be removed.
   * 
   * To be used when removing last element from LinkedList.
   * 
   * @return head element.
   */
  public E clear() {
    E headData = this.get(1);
    head = null;
    tail = null;
    listSize = 0;
    return headData;
  }
 
  /**
   * Add a node with element data to end of LinkedList.
   *
   * @param data - element to be stored
   */   
  public void addToTail(E data) {
 
    Node<E> newNode = new Node<>(data);
    if (this.isEmpty()) {
      this.head = newNode;
      this.tail = head;
    } else {
      (this.tail).setNext(newNode);
      this.tail = newNode;
    }
    this.listSize++;
  }
 
  /**
* Add a node with element data to front of LinkedList.
 
   *
   * @param data - element to be stored
   */
  public void addToHead(E data) {
    Node<E> newNode = new Node<>(data);
    if (this.isEmpty()) {
      this.head = newNode;
      this.tail = head;
    } else {
      newNode.setNext(this.head);
      this.head = newNode;
    }
    this.listSize++;
  }
 
  /**
   * Add a node after a specific index.
   * 
   * index = 0 to add to front, n to add after element n.
   * 
   * @param data - element to be store
   * @param index - point at which to add data
   */ 
  public void addAfterIndex(E data, int index) {
 
    if (index <= 0) { 
      this.addToHead(data);
    } else if (index >= this.size())  {
      this.addToTail(data);
    } else {
 
      Node<E> newNode = new Node<>(data);
 
      // Traverse to the Node that we want to insert after
      Node<E> targetNode = this.head;
 
      for (int i = 1; i < index; i++) {
        targetNode = targetNode.getNext();
      }
 
      newNode.setNext(targetNode.getNext());
      targetNode.setNext(newNode);
      this.listSize++;
 
    }
  }
 
  /**
   * Returns object at the specified position of LinkedList.
   *
   * @param index - index of element to retrieve.
   * @return element at that index.
   */
  public E get(int index) {
    if (index <= 0 || index > size()) {
      return null;
    }
 
    Node<E> currentNode = this.head;
    for (int i = 1; i < index; i++) {
      currentNode = currentNode.getNext();
    }
    return currentNode.getData();
  }
 
  /**
   * Remove from the tail end of LinkedList.
   * 
   * @return data stored in tail Node.
   */
  public E removeTail() {
 
    if (this.isEmpty()) {
      return null;
    } else if (this.size() == 1) {
      return this.clear();
    } else {
 
      Node<E> previousNode = this.head;
      for (int i = 1; i < size()-1; i++) {
        previousNode = previousNode.getNext();
      }
  
      E returnData = get(this.size());
      previousNode.setNext(null);
      this.tail = previousNode;
  
      listSize--;
      return returnData;
    }
  }
 
  /**
   * Remove from the front of the LinkedList.
   * 
   * @return data contained in head node.
   */
  public E removeHead() {
    // If nothing inside of the LinkedList
    if (isEmpty()) {
      return null;
    } else if (size() == 1) {
      return clear();
    } else {
      E headData = get(1);
      this.head = head.getNext();
      this.listSize--;
      return headData;
    }
  }
    
  /**
   * Remove from a specified index in LinkedList.
   * 
   * @return data contained at the index.
   */ 
  public E removeAtIndex(int index) {
    if (index <= 1) {
      return removeHead();
    } else if (index >= size()) { 
      return removeTail();
    } else {
      Node<E> previousNode = this.head;
 
// Reaches to the previous of the node we  want to remove
      for (int i = 1; i < index - 1; i++) {
        previousNode = previousNode.getNext();
      }
      E nodeData = previousNode.getNext().getData();
      previousNode.setNext(previousNode.getNext().getNext());
      listSize--;
      return nodeData;
    }
  }
 
  public void insert(E[] testInput) {
 
    for (int i = 0; i < testInput.length; i++) {
      this.addToTail(testInput[i]);
    }
    
  }
  
 
}

Learn Enterprise Java Development for a Bright Career

Head First Java

Learn Enterprise Java Development for a Bright Career Try Java

Jump start your Java education with Head First Java! This book provides clean diagram examples, with text that is easy-to-understand in an almost too-casual language. Great for anyone new to Java or programming in general.

$ Check price
44.9544.95Amazon 4.5 logo(567+ reviews)

More Java resources

Learn how data is stored

Data Structures and Algorithms Made Easy

Learn how data is stored Try Data Structures

A handy guide of sorts for any computer science professional, Data Structures And Algorithms Made Easy in Java: Data Structure And Algorithmic Puzzles is a solution bank for various complex problems related to data structures and algorithms. It can be used as a reference manual by those readers in the computer science industry.

$ Check price
39.9939.99Amazon 4.5 logo(339+ reviews)

More Data Structures resources

Ad