Linked-list in Java

a minimal linked-list

Overview

A linked-list is a linear data structure, in which the elements are not stored at contiguous memory locations. The elements in a linked-list are linked using references.

Motivation

• Alternative to array to store a sequence of data
• Fast to add/remove at the beginning or in the middle of the list

Variations

• Singly linked-list
• Doubly linked-list
• Circular linked-list (optional)
• With or without dummy head node (optional)

Components

• Head/first variable

  • reference to the first node in the linked-list
  • can be null if the linked-list is empty

• Tail/last viable

  • reference to the last node in the linked-list
  • can be null if the linked-list is empty
  • optional, can improve performance when the tail nodes needs to be accessed frequently

• Node class (nested private class)

  // Node class for singly linked-list
  // access modifiers for members in the nested class does not matter mostly
  private class Node {
    int data;
    Node next;
  }
  
  // node class for doubly linked-list
  private class Node {
    int data;
    Node prev;
    Node next;
  }
  

• Behaviors (methods)

  • void addFirst(T data)
  • void addLast(T data)
  • void removeFirst()
  • void removeLast()
  • void insertAfter(int data, T index)
  • void insertBefore(int data, T index)
  • void remove(int index)
  • T get(int index)
  • void set(int index, T data)
  • boolean contains(T data)
  • int size()
  • boolean isEmpty()
  • String toString()

• Try list operations in our ADT Explorer, then check visualgo.net for another view.

• Check Code examples