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

Property	Linked-list	Array
Data structure	Linear	Linear
Memory usage	More	Less;Continuous
Random access	Slow	Fast
Insertion/deletion	Fast	Slow
Size	Dynamic	Static

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()

• Check visualgo.net for more details

• Check Code examples