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]);
    }
    
  }
  
 
}

Want to avoid becoming a code monkey?

Code Complete 2

Want to avoid becoming a code monkey? Try Good Practice

This book synthesizes the most effective techniques and must-know principles into clear, pragmatic guidance. No matter what your experience level, development environment, or project size, this book will inform and stimulate your thinking - and help you build the highest quality code.

$ Check price
54.9954.99Amazon 4.5 logo(291+ reviews)

More Good Practice resources

Ace your Technical Interview

Cracking the Coding Interview

Ace your Technical Interview Try Algorithms

Cracking the Coding Interview will tell you exactly what you need to know to land your dream job at Google, Amazon, Microsoft or any other big tech companies. Packed with over 189 interview questions and detailed solutions, this book will help you train for the classic white-board technical interview. A must have for any CS major.

$ Check price
39.9539.95Amazon 4.5 logo(266+ reviews)

More Algorithms resources

Ad