實作_資料結構_單向鏈結串列_可儲存 int型態資料

SinglyLinkedList.java

public class SinglyLinkedList {
  private Node head;

  private class Node {
    int data;
    Node next;
  }

  public SinglyLinkedList() {

  }

  public int size() {
    if (isEmpty()) {
      return 0;
    }

    int size = 0;
    Node currentNode = head;
    while (true) {
      size += 1;
      if (currentNode.next == null) {
        break;
      }
      currentNode = currentNode.next;
    }

    return size;
  }

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

  /**
   * 
   * @param index
   *          從0開始
   * @return null表示指定的索引位置不存在資料
   */
  public Integer get(int index) {
    if (isEmpty()) {
      return null;
    }

    int currentIndex = -1;
    Node currentNode = head;
    Integer data = null;
    while (true) {
      currentIndex += 1;
      if (currentIndex == index) {
        data = currentNode.data;
        break;
      }
      if (currentNode.next == null) {
        break;
      }
      currentNode = currentNode.next;
    }

    return data;
  }

  /**
   * 將資料插入到最後一個位置
   * 
   * @param data
   * @return
   */
  public boolean add(int data) {
    Node newNode = new Node();
    newNode.data = data;
    newNode.next = null;

    if (isEmpty()) {
      head = newNode;
      return true;
    }

    Node lastNode = getLastNode();
    lastNode.next = newNode;

    return true;
  }

  /**
   * 將資料插入指定索引位置
   * 
   * @param index
   * @param node
   * @return
   */
  public boolean add(int index, int data) {
    Node newNode = new Node();
    newNode.data = data;
    newNode.next = null;

    if (isEmpty()) {
      head = newNode;
      return true;
    }

    if (index == 0) {
      newNode.next = head;
      head = newNode;
      return true;
    }

    Node preNode = null;
    Node currentNode = head;
    int currentIndex = -1;
    while (true) {
      currentIndex += 1;
      if (currentIndex == index) {
        break;
      }
      if (currentNode.next == null) {
        break;
      }
      preNode = currentNode;
      currentNode = currentNode.next;
    }

    if (currentIndex != index) {// 指定索引不存在
      return false;
    }

    newNode.next = currentNode;
    preNode.next = newNode;

    return true;
  }

  private Node getLastNode() {
    Node currentNode = head;
    while (true) {
      if (currentNode.next == null) {
        break;
      }
      currentNode = currentNode.next;
    }
    return currentNode;
  }

  public Integer removeLast() {
    if (isEmpty()) {
      return null;
    }

    Integer value;

    if (head.next == null) {
      value = head.data;
      head = null;
      return value;
    }

    Node preNode = null;
    Node currentNode = head;
    while (true) {
      if (currentNode.next == null) {
        break;
      }
      preNode = currentNode;
      currentNode = currentNode.next;
    }

    value = currentNode.data;

    currentNode = null;
    preNode.next = null;

    return value;
  }

  public Integer remove(int index) {
    if (index < 0) {
      return null;
    }

    if (isEmpty()) {
      return null;
    }

    Integer value;

    if (index == 0 && head.next == null) {
      value = head.data;
      head = null;
      return value;
    } else if (index == 0 && head.next != null) {
      value = head.data;
      head = head.next;
      return value;
    } else if (index > 0 && head.next == null) {
      return null;
    }

    Node preNode = null;
    Node currentNode = head;
    int currentIndex = -1;
    while (true) {
      currentIndex += 1;
      if (currentIndex == index) {
        break;
      }
      if (currentNode.next == null) {
        break;
      }
      preNode = currentNode;
      currentNode = currentNode.next;
    }

    if (currentIndex != index) {// 指定索引不存在
      return null;
    }

    value = currentNode.data;

    preNode.next = currentNode.next;
    currentNode = null;

    return value;
  }
}