package 數(shù)據(jù)結(jié)構(gòu)算法.鏈表;

/*
 *定義節(jié)點(diǎn)
 * 鏈表由節(jié)點(diǎn)構(gòu)成
 */
public class Node<E> {
  private E e;  //數(shù)據(jù)data
  private Node<E> next; //指向下一個(gè)節(jié)點(diǎn)

  public Node() {

  }

  public Node(E e) {
    this.e = e;
  }

  public Node<E> getNext() {
    return next;
  }

  public void setNext(Node<E> next) {
    this.next = next;
  }

  public E getE() {
    return e;
  }

  public void setE(E e) {
    this.e = e;
  }
}

package 數(shù)據(jù)結(jié)構(gòu)算法.鏈表;

/*
 * 定義實(shí)現(xiàn)類MyLinkedList
　*　實(shí)現(xiàn)鏈表的基本功能：增刪改查
 */
public class MyLinkedList<E> {
  //聲明頭節(jié)點(diǎn)尾節(jié)點(diǎn)
  private Node<E> head;
  private Node<E> last;
  //鏈表的大小
  private int size;
  private int modcount; //計(jì)算被修改的次數(shù)

  public MyLinkedList() {
    head = new Node<E>();//實(shí)例化頭結(jié)點(diǎn)
    last = head;
  }

  /*
   *返回單鏈表中存儲(chǔ)的元素總數(shù)
   */
  public int size() {
    return size;
  }

  /*
   *獲取指定索引位置的節(jié)點(diǎn)對(duì)象
   */
  public Node<E> get(int index) {
    if (index < 0 || index > size - 1)
      return null;
    Node<E> node = head.getNext();//將頭結(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)賦給Node
    for (int i = 0; i < index; i++) {
      node = node.getNext();//獲取node的下一個(gè)節(jié)點(diǎn)
    }
    return node;
  }

  /*
   *獲取指定索引位置的數(shù)據(jù)
   */
  public E getValue(int index) {
    if (index < 0 || index > size - 1)
      return null;
    Node<E> node = get(index);
    return node.getE();
  }

  /*
   *增加元素
   */
  public void add(E e) {
    Node<E> node = new Node<E>(e); //以e實(shí)例化一個(gè)節(jié)點(diǎn)
    last.setNext(node);//往尾節(jié)點(diǎn)后追加節(jié)點(diǎn)
    last = node;//該節(jié)點(diǎn)設(shè)為最后一個(gè)節(jié)點(diǎn)
    size++;
    modcount++;
  }

  /*
   *指定位置插入元素,返回插入的節(jié)點(diǎn)數(shù)據(jù)
   */
  public E add(int index, E e) {
    if (index < 0 || index > size - 1)
      return null;
    Node<E> node = new Node<E>(e); //實(shí)例化一個(gè)節(jié)點(diǎn)
    //找到插入的原節(jié)點(diǎn)
    Node<E> oldNode = get(index);
    if (index == 0) {//當(dāng)索引為0時(shí)
      head.setNext(node);
    } else {
      //找到插入節(jié)點(diǎn)的上一個(gè)
      Node<E> bNode = get(index - 1);
      bNode.setNext(node);
    }
    node.setNext(oldNode);
    size++;
    modcount++;
    return oldNode.getE();
  }

  /*
   *刪除指定的節(jié)點(diǎn)e,并返回刪除節(jié)點(diǎn)的數(shù)據(jù)
   */
  public E delete(int index) {
    if (index < 0 || index > size - 1)
      return null;
    if (index == 0) {//當(dāng)索引為1，令頭結(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)為頭結(jié)點(diǎn)
      Node<E> node = head.getNext();
      head.setNext(node.getNext());
    }
    //獲取要?jiǎng)h除節(jié)點(diǎn)的前一個(gè)節(jié)點(diǎn)
    Node<E> bNode = get(index - 1);
    //獲取要?jiǎng)h除的節(jié)點(diǎn)
    Node<E> Node = bNode.getNext();
    //獲取要?jiǎng)h除節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)
    Node<E> nNode = Node.getNext();
    //刪除該節(jié)點(diǎn)
    bNode.setNext(nNode);
    //清除Node的下一個(gè)節(jié)點(diǎn)
    Node.setNext(null);
    size--;
    modcount++;
    return Node.getE();//返回節(jié)點(diǎn)中的數(shù)據(jù)域
  }

  /*
   *修改指定位置的數(shù)據(jù)域并返回修改后的數(shù)據(jù)
   */
  public E set(int index, E e) {
    if (index < 0 || index > size - 1)
      return null;
    //獲取指定位置的原節(jié)點(diǎn)
    Node<E> node = get(index);
    node.setE(e);
    modcount++;
    return node.getE();
  }
}

package 數(shù)據(jù)結(jié)構(gòu)算法.鏈表;

/*
 *定義測試類
 */
public class MyLinkedListTest {
  public static void main(String[] args) {
    MyLinkedList<String> list = new MyLinkedList<>();

    //測試add
    list.add("one");
    list.add("two");
    list.add("three");
    list.add("four");
    list.add(0,"newone");
    list.add(1,"newtwo");
    for (int i = 0; i < list.size(); i++) {
      System.out.print(list.getValue(i)+" ");
    }

    //測試set
    System.out.println();
    list.set(0, "111");
    list.set(1, "222");
    System.out.println(list.getValue(0) + "  " + list.getValue(1));

    //測試delete
    System.out.println();
    list.delete(1);
    for (int i = 0; i < list.size(); i++) {
      System.out.print(list.getValue(i)+" ");
    }
  }
}