Java数据结构之链表、栈、队列、树的实现方法示例

链表

链表是一种线性数据结构，由节点的集合构成。每个节点包含两部分，数据部分和指针部分。数据部分用于存储数据，指针部分用于指向下一个节点。

单向链表示例

public class LinkedList<E>{
  private Node<E> head;
  private int size;

  private static class Node<E>{
    E item;
    Node<E> next;
    public Node(E item,Node<E> next){
      this.item = item;
      this.next = next;
    }
  }

  public void add(E item){
    head = new Node<>(item,head);
    size++;
  }

  public E remove(){
    if(head == null) throw new NoSuchElementException();
    E item = head.item;
    head = head.next;
    size--;
    return item;
  }
}

双向链表示例

public class DoublyLinkedList<E>{
  private Node<E> head;
  private Node<E> tail;
  private int size;

  private static class Node<E>{
    E item;
    Node<E> next;
    Node<E> prev;
    public Node(E item,Node<E> next,Node<E> prev){
      this.item = item;
      this.next = next;
      this.prev = prev;
    }
  }

  public void addFirst(E item){
    Node<E> newNode = new Node<>(item,head,null);
    if(head == null){
      head = tail = newNode;
    } else {
      head.prev = newNode;
      head = newNode;
    }
    size++;
  }

  public void addLast(E item){
    Node<E> newNode = new Node<>(item,null,tail);
    if(tail == null){
      head = tail = newNode;
    } else {
      tail.next = newNode;
      tail = newNode;
    }
    size++;
  }

  public E removeFirst(){
    if(head == null) throw new NoSuchElementException();
    E item = head.item;
    head = head.next;
    head.prev = null;
    size--;
    return item;
  }

  public E removeLast(){
    if(tail == null) throw new NoSuchElementException();
    E item = tail.item;
    tail = tail.prev;
    tail.next = null;
    size--;
    return item;
  }
}

栈

栈是一种线性数据结构，只能在一端插入、删除元素，这一端被称为栈顶。后进先出（LIFO）是它的典型特点。

数组实现示例

public class ArrayStack<E>{
  private E[] stack;
  private int top;
  private int capacity;

  @SuppressWarnings("unchecked")
  public ArrayStack(int capacity){
    this.capacity = capacity;
    stack = (E[]) new Object[capacity];
    top = -1;
  }

  public void push(E item){
    if(top == capacity - 1) throw new StackOverflowError();
    stack[++top] = item;
  }

  public E pop(){
    if(top == -1) throw new EmptyStackException();
    return stack[top--];
  }

  public E peek(){
    if(top == -1) throw new EmptyStackException();
    return stack[top];
  }

  public boolean isEmpty(){
    return top == -1;
  }

  public boolean isFull(){
    return top == capacity - 1;
  }
}

链表实现示例

public class LinkedListStack<E>{
  private Node<E> top;
  private int size;

  private static class Node<E>{
    E item;
    Node<E> next;
    public Node(E item,Node<E> next){
      this.item = item;
      this.next = next;
    }
  }

  public void push(E item){
    top = new Node<>(item,top);
    size++;
  }

  public E pop(){
    if(top == null) throw new EmptyStackException();
    E item = top.item;
    top = top.next;
    size--;
    return item;
  }

  public E peek(){
    if(top == null) throw new EmptyStackException();
    return top.item;
  }

  public boolean isEmpty(){
    return top == null;
  }

  public int size(){
    return size;
  }
}

队列

队列是一种线性数据结构，支持在队尾插入元素，在队首删除元素，先进先出（FIFO）是它的典型特点。

数组实现示例

public class ArrayQueue<E>{
  private E[] queue;
  private int front;
  private int rear;
  private int capacity;

  @SuppressWarnings("unchecked")
  public ArrayQueue(int capacity){
    this.capacity = capacity;
    queue = (E[]) new Object[capacity];
    front = rear = -1;
  }

  public void enqueue(E item){
    if(rear == capacity - 1) throw new RuntimeException("Queue full");
    queue[++rear] = item;
    if(front == -1) front = 0;
  }

  public E dequeue(){
    if(front == -1 || front > rear) throw new RuntimeException("Queue empty");
    E item = queue[front++];
    if(front > rear) front = rear = -1;
    return item;
  }

  public E peek(){
    if(front == -1 || front > rear) throw new RuntimeException("Queue empty");
    return queue[front];
  }

  public boolean isEmpty(){
    return front == -1 || front > rear;
  }

  public boolean isFull(){
    return rear == capacity - 1;
  }

  public int size(){
    if(front == -1) return 0;
    return rear - front + 1;
  }
}

链表实现示例

public class LinkedListQueue<E>{
  private Node<E> head;
  private Node<E> tail;

  private static class Node<E>{
    E item;
    Node<E> next;
    public Node(E item,Node<E> next){
      this.item = item;
      this.next = next;
    }
  }

  public void enqueue(E item){
    Node<E> newNode = new Node<>(item,null);
    if(head == null){
      head = tail = newNode;
    } else {
      tail.next = newNode;
      tail = newNode;
    }
  }

  public E dequeue(){
    if(head == null) throw new NoSuchElementException();
    E item = head.item;
    head = head.next;
    if(head == null) tail = null;
    return item;
  }

  public E peek(){
    if(head == null) throw new NoSuchElementException();
    return head.item;
  }

  public boolean isEmpty(){
    return head == null;
  }
}

树

树是一种非线性数据结构，由节点和边组成。每个节点只有一个父节点，但是可以有多个子节点。根节点是没有父节点的特殊节点。

二叉搜索树示例

public class BinarySearchTree<E extends Comparable<? super E>>{
  private TreeNode<E> root;

  private static class TreeNode<E>{
    E item;
    TreeNode<E> left;
    TreeNode<E> right;
    public TreeNode(E item){
      this.item = item;
    }
  }

  public void insert(E item){
    root = insert(root,item);
  }

  private TreeNode<E> insert(TreeNode<E> node,E item){
    if(node == null) return new TreeNode<>(item);
    int compareResult = item.compareTo(node.item);
    if(compareResult < 0){
      node.left = insert(node.left,item);
    } else if(compareResult > 0){
      node.right = insert(node.right,item);
    }
    return node;
  }

  public void remove(E item){
    root = remove(root,item);
  }

  private TreeNode<E> remove(TreeNode<E> node,E item){
    if(node == null) return null;
    int compareResult = item.compareTo(node.item);
    if(compareResult < 0){
      node.left = remove(node.left,item);
    } else if(compareResult > 0){
      node.right = remove(node.right,item);
    } else {
      if(node.left != null && node.right != null){
        node.item = findMin(node.right).item;
        node.right = remove(node.right,node.item);
      } else {
        node = node.left != null ? node.left : node.right;
      }
    }
    return node;
  }

  private TreeNode<E> findMin(TreeNode<E> node){
    if(node == null) return null;
    while(node.left != null){
      node = node.left;
    }
    return node;
  }

  private TreeNode<E> findMax(TreeNode<E> node){
    if(node == null) return null;
    while(node.right != null){
      node = node.right;
    }
    return node;
  }

  public boolean contains(E item){
    return contains(root,item);
  }

  private boolean contains(TreeNode<E> node,E item){
    if(node == null) return false;
    int compareResult = item.compareTo(node.item);
    if(compareResult < 0){
      return contains(node.left,item);
    } else if(compareResult > 0){
      return contains(node.right,item);
    } else {
      return true;
    }
  }
}

以上就是Java数据结构之链表、栈、队列、树的实现方法示例的详细攻略。