数据结构之链表

 // 节点作为链表的内部类设计
  private class Node {
    // 存放在节点中的类型,数据
    public E e;
    // 指向下一个节点的变量
    // 下一个节点也是node,这是节点设计中最重要的一环
    public Node next;


    // 提供构造方法1
    public Node(E e, Node next) {
      this.e = e;
      // 构造的这个新的节点,直接指向用户传进来的这个节点
      this.next = next;
    }


    // 构造方法2
    public Node(E e) {
      // 如果只传数据,那么这个节点不指向任何节点,
      this(e, null);
    }


    // 提供无参构造
    public Node() {
      this(null, null);
    }


    public String toString() {
      return e.toString();
    }
  }

public class LinkedList<E> {
  //内部类
  //................


  //链表的框架设计
  private Node head;//头结点
  private int size;//链表长度
  
  //提供构造函数
  public LinkedList(){
    head = new Node();
    size = 0;
  }
  
  //获取链表中的元素个数
  public int getSize(){
    return size;
  }
  
  //判断链表是否为空
  public boolean isEmpty(){
    return size == 0;
  }
}

  //在链表的头部添加
  public void addFirst(E e){
    //构造线性节点
    Node node = new Node(e);
    //让这个节点的下一个节点指向头节点
    node.next = head;
    //维护头节点
    head = node;
    //维护size
    size++;
    
    //根据节点的构造Node(E e, Node next)
    //前三行代码可写成
    
    //head = new Node(e,head);
  }

  public void add(E e,int index){
      //判断要插入位置的有效性
      if(index < 0 || index > size){
          throw new IllegalArgumentException("Add failed. Illegal index");
      }
    
    //先判断是否为头节点
    if(index == 0){
      addFirst(e);
    }else{
      //1.定义插入位置的前一个节点(默认位置头节点)
      Node prev = head;
      //2.寻找prev的位置
      //!!!循环此链表,寻找需要插入位置的前一个节点
      //就是把头结点(prev,head),向后推,移动index- 1次
      //就到了需要插入节点位置的前一个
      for(int i = 0;i < index -1;i++){
        //找到插入位置的前一个节点
        prev = prev.next;
      }
      
      //构造待插入节点
          Node node = new Node(e);
          //插入节点指向prev的下一个节点(插入位置节点)
          node.next = prev.next;
          //prev节点的指向的下一个节点就是插入节点
          prev.next = node;
          size++;
          //三行合并
          prev.next = new Node(e,prev.next);
    }
  }

public LinkedList<E>{
   private Node dummyHead;//虚拟头结点
    private int size;
    
    //设置构造
    public LinkedList(){
        //初始化时是一个节点
        dummyHead = new Node(null, null);
        size = 0;
    }
    //添加操作
    public void add(int index, E e){
        
        //此位置判断位置的有效性,省略
        //..........
        
        //1.定义要插入节点的前一个节点
        Node prev = dummyHead;
        //遍历寻找prev的位置,如果要插入的头节点,这样的话,头节点也有前一个节点
        //就是dummyHead
        //因为是虚拟节点(头节点的前一个节点),
        //所以比之前还要多向后移一下      
        for(int i = 0 ; i < index; i++){
            prev = prev.next;
        }
        
        prev.next = new Node(e, prev.next);
        size++;
    } 
    
    //添加头
    public void addFirst(E e){
        add(0, e);
    }  
    
    // 在链表末尾添加新的元素e
    public void addLast(E e){
        add(size, e);
    }
}

  public E get(int index){
    //获取指定位置元素
    //判断输入位置的正确性
    //定义需要查找位置的节点
      //因为查找是从第一个位置开始的,所以定义的时候
      //从虚拟头结点的下一个(就是真正的头节点开始)
    Node cur = dummyHead.next;
    //遍历到指定节点
    for(int i = 0;i <index;i++){
      cur = cur.next;
    }
    return cur.e;
  }
  
    // 获取第一个位置的元素
  public E getFirst() {
    return get(0);
  }


  // 获取最后一个
  public E getLast() {
    return get(size - 1);
  }

  public void set(int index, E e){
      //判断传入位置的正确性
      //......
      
      //同获取一样,先得要需要修改节点的位置
      Node cur = dummyHead.next;
      for(int i= 0; i < index; i++){
          cur = cur.next;
      }
      cur.e = e;
  }

  //判断链表中是否包含元素
  public boolean contains(E e){
    //定义当前节点
    Node cur = dummyHead.next;
    //整条链表遍历
    for(int i = 0; i< size;i++){
      //如果找到,直接return,退出函数
      if(cur.e.equals(e)){
              return true;
          }
    }
    return false;
  }

  //删除指定位置元素,返回删除元素
  public E remove(int index){
    //判断传入位置的正确性
      //......
    
    //定义删除位置的前一个节点
    Node prev = dummyHead;
    //遍历找到删除位置
    for(int i = 0; i< index;i++){
      prev = prev.next;
    }
    //保存需要删除的节点,一遍作为返回
    Node retNode = prev.next;
    //让删除节点的前一个节点直接指向要删除节点的后一个节点
    prev.next = retNode.next;
    //删除元素脱离链表
    retNode.next = null;
    //维护size
    size--;  
    return retNode.e;    
  }