[数据结构与算法]数据结构-链表（java）

链表

• 动态数组有个明显的缺点
  • 可能会造成内存空间的大量浪费
• 能否用到多少就申请多少内存？
  • 链表可以办到这一点
• 链表是一种链式存储的线性表，所有元素的内存地址不一定是连续的

链表的设计

接口设计

• 链表的大部分接口和动态数组是一致的

清空元素-clear()

@Override
public void clear() {
    size=0;
    first=null;
}

链表实现

AbstractList.java

public abstract class AbstractList<E> implements List<E>  {
	/**
	 * 元素的数量
	 */
	protected int size;
	/**
	 * 元素的数量
	 * @return
	 */
	public int size() {
		return size;
	}

	/**
	 * 是否为空
	 * @return
	 */
	public boolean isEmpty() {
		 return size == 0;
	}

	/**
	 * 是否包含某个元素
	 * @param element
	 * @return
	 */
	public boolean contains(E element) {
		return indexOf(element) != ELEMENT_NOT_FOUND;
	}

	/**
	 * 添加元素到尾部
	 * @param element
	 */
	public void add(E element) {
		add(size, element);
	}
	
	protected void outOfBounds(int index) {
		throw new IndexOutOfBoundsException("Index:" + index + ", Size:" + size);
	}
	
	protected void rangeCheck(int index) {
		if (index < 0 || index >= size) {
			outOfBounds(index);
		}
	}
	
	protected void rangeCheckForAdd(int index) {
		if (index < 0 || index > size) {
			outOfBounds(index);
		}
	}
}

LinkedList.java

public class LinkedList<E> extends AbstractList<E>{
    private Node<E> first;
    private static class Node<E> {
        E element;
        Node<E> next;
        public Node(E element,Node<E> next) {
            this.element=element;
            this.next=next;
        }
    }
    @Override
    public void clear() {
        size=0;
        first=null;
    }


    @Override
    public boolean contains(E element) {
        return indexOf(element)!=ELEMENT_NOT_FOUND;
    }


    @Override
    public E get(int index) {
        return node(index).element;
    }

    @Override
    public E set(int index, E element) {
        Node<E> node = node(index);
        E old=node.element;
        node.element=element;
        return old;
    }

    @Override
    public void add(int index, E element) {
        rangeCheckForAdd(index);
        if(index==0) {
            first=new Node<>(element,first);
        }else {
            Node<E> prev = node(index - 1);
            prev.next = new Node<>(element, prev.next);
        }
        size++;
    }

    @Override
    public E remove(int index) {
        rangeCheck(index);
        Node<E> node=first;
        if(index==0){
            first=first.next;
        }else {
            Node<E> prev = node(index - 1);
            node=prev.next;
            prev.next = prev.next.next;
        }
        size--;
        return node.element;
    }

    @Override
    public int indexOf(E element) {
        if(element==null){
            Node<E> node=first;
            for(int i=0;i<size;i++){
                if(node.element==null)return i;
                node=node.next;
            }
        }else {
            Node<E> node = first;
            for(int i=0;i<size;i++){
                if(element.equals(node.element))return i;
                node=node.next;
            }
        }
        return ELEMENT_NOT_FOUND;
    }

    /**
     * 获取index位置对应的节点对象
     * @param index
     * @return
     */
    private Node<E> node(int index){
        rangeCheck(index);
        Node<E> node = first;
        for(int i=0;i<index;i++){
            node=node.next;
        }
        return node;
    }

    @Override
    public String toString() {
        StringBuilder string = new StringBuilder();
        string.append("size=").append(size).append(",[");
        Node<E> node = first;
        for(int i=0;i<size;i++){
            if(i!=0){
                string.append(",");
            }
            string.append(node.element);
            node=node.next;
        }
        string.append("]");
        return string.toString();
    }
}

虚拟头节点

有时候为了让代码更加精简，统一所有节点的处理逻辑，可以在最前面增加一个虚拟的头节点（不存储数据）

动态数组、链表复杂度分析

双向链表

• 使用双向链表可以提升链表的综合性能

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

• clear()

  @Override
  public void clear() {
      size=0;
      first=null;
      last=null;
  }
  

• add()

  public void add(int index, E element) {
      rangeCheckForAdd(index);
  
      if(index==size){
          Node<E> oldLast = last;
          last = new Node<>(oldLast,element,null);
          if(oldLast==null){
              first=last;
          }else {
              oldLast.next=last;
          }
      }else{
              Node<E> next = node(index);
              Node<E> prev = next.prev;
              Node<E> node = new Node<>(prev, element, next);
              next.prev = node;
              if (prev == null) {
                  first = next;
              } else {
                  prev.next = next;
              }
          }
      size++;
  }
  

双向链表VS动态数组

• 动态数组：开辟、销毁内存空间的次数相对较少，但可能造成内存空间浪费（可通过缩容解决）

• 双向链表：开辟、销毁内存空间的次数相对较多，但不会造成内存空间的浪费

• 如果频繁在尾部进行添加、删除操作，动态数组、双向链表均可选择

• 如果频繁在头部进行添加、删除操作，建议选择使用双向链表

• 如果有频繁的（在任意位置）添加、删除操作，建议选择使用双向链表

• 如果有频繁的操作操作（随机访问操作），建议选择使用动态数组

单向循环链表

• add()

  	    @Override
      public void add(int index, E element) {
          rangeCheckForAdd(index);
          if(index==0) {
              Node<E> newfirst=new Node<>(element,first);
              //拿到最后一个节点
              Node<E> last = (size==0) ? newfirst : node(size-1);
              last.next=newfirst;
              first=newfirst;
          }else {
              Node<E> prev = node(index - 1);
              prev.next = new Node<>(element, prev.next);
          }
          size++;
      }
  

• remove()

  @Override
  public E remove(int index) {
      rangeCheck(index);
      Node<E> node=first;
      if(index==0){
          if(size==1){
              first=null;
          }else {
              Node<E> last = node(size-1);
              first=first.next;
              last.next=first;
          }
      }else {
          Node<E> prev = node(index - 1);
          node=prev.next;
          prev.next = prev.next.next;
      }
      size--;
      return node.element;
  }
  

双向循环链表

• add()

  	    @Override
      public void add(int index, E element) {
          rangeCheckForAdd(index);
  
          if(index==size){
              Node<E> oldLast = last;
              last = new Node<>(oldLast,element,first);
              if(oldLast==null){
                  first=last;
                  first.next=first;
                  first.prev=first;
              }else {
                  oldLast.next=last;
                  first.prev=last;
              }
          }else{
                  Node<E> next = node(index);
                  Node<E> prev = next.prev;
                  Node<E> node = new Node<>(prev, element, next);
                  next.prev = node;
                  prev.next = node;
                  if (index==0) {
                      first = next;
                  }
              }
          size++;
      }
  

• remove()

  	    @Override
      public E remove(int index) {
          rangeCheck(index);
          Node<E> node=first;
          if(size==1){
              first=null;
              last=null;
          }else {
              node = node(index);
              Node<E> prev = node.prev;
              Node<E> next = node.next;
              prev.next = next;
              next.prev = prev;
  
              if (node == first) {
                  first = next;
              }
              if (node == last) {
                  last = prev;
              }
          }
          size--;
          return node.element;
      }
  

如何发挥循环链表的最大威力

• 可以考虑增设1个成员变量、3个方法

• current：用于指向某个节点

• void reset()：让current指向头节点first

• E next()：让current往后走一步，也就是current=current.next

• E remove()：删除current指向的节点，删除成功后让current指向下一个节点

• 	    @Override
      public E remove(int index) {
          rangeCheck(index);
          return remove(node(index));
      }
    
      public E remove(){
          if(current==null)return null;
          Node<E> next = current.next;
          E element = remove(current);
          if(size==0){
              current=null;
          }else{
              current=next;
          }
          return element;
      }
      private E remove(Node<E> node){
          if(size==1){
              first=null;
              last=null;
          }else {
              Node<E> prev = node.prev;
              Node<E> next = node.next;
              prev.next = next;
              next.prev = prev;
    
              if (node == first) {
                  first = next;
              }
              if (node == last) {
                  last = prev;
              }
          }
          size--;
          return node.element;
      }
          public void reset(){
          current=first;
      }
      public E next(){
          if(current==null)return null;
          current=current.next;
          return current.element;
      }
  

静态链表

用数组模拟链表，称为静态链表

数组的每个元素存放2个数据：值、下个元素的索引

数据0位置存放的是头节点信息