04.Java数据结构与算法之~双链表

LinkedList底层原理

       LinkedList底层是一个双向链表；添加、删除元素效率高；按照索引查询效率低。可以两个方向查询

       每个节点都包含了对前一个和后一个元素的引用

       LinkedList同时实现了List、Deque、Queue接口，所以可以当做线性表、队列、双端队列、栈使用

       LinkedList 是非同步的（线程不安全）

       不存在LinkedList容量不足的问题

双链表的添加过程

双向链表:遍历效率可能优于单向链表

定义List接口

public interface List <E>{ int size(); boolean isEmpty(); boolean contains(E element); void add(E element);     E get(int index);     E set(int index,E element); void add(int index,E element);     E remove(int index); int indexOf(E element); void clear();     String toString(); } 

实现List接口

public class LinkedList<E> implements List<E>{ private int size; //集合的长度 private Node first; private Node last; @Override public int size() { return size; } //判断当前集合中是否有元素 @Override public boolean isEmpty() { return size == 0; } //判断当前元素是否存在 @Override public boolean contains(E element) { return indexOf(element) > -1; } @Override public void add(E element) { //调用下面的add方法,根据size保证每次都添加在最后 add(size,element); } //取得坐标位置上的节点 private Node<E> node(int index){         Node N = first; //指向头 //先判断要查找的index,是靠近头还是靠近尾 //如果靠近头就从头开始查找,如果靠近尾就从尾开始查找 //方法: 根据index 和 size的一半去比较 if(index > (size >> 1)){ //靠近尾             N = last; //指向尾 for(int i = size-1; i > index; i--){                 N = N.pre; } }else{ //靠近头 for(int i = 0; i < index; i++){                 N = N.next; } } return N; } @Override public E get(int index) { //防止坐标越界 if(index < 0 || index >= size){ throw new IndexOutOfBoundsException("index： " + index + " size: " + size); } //调用方法 return node(index).element; } @Override public E set(int index, E element) { //获得index上的node         Node<E> node = node(index); //保存原来的值         E oldElement = node.element; //新值覆盖老值         node.element = element; //返回老值 return oldElement; } @Override public void add(int index, E element) { //当需要添加到末尾时 if(index == size) { //拿到last节点             Node l = last; //构建node 完成指向关系             Node newNode = new Node(l,null,element); //将原来的last 节点的next 修改成新构建出来的node             last = newNode; if(l == null){                 first = newNode; }else {                 l.next = newNode; } }else{ //获得指定的index             Node<E> node = node(index); //获得前一个结点             Node<E> pre = node.pre; //构建新的now 完成指向关系             Node<E> newNode = new Node(pre, node, element); //改变指向             pre.next = newNode; if (pre == null) {                 first = newNode; } else {                 node.pre = newNode; } }         size++; } //链表删除的主要原理就是将被删除者的前一个元素指向后一个元素 //比如 A->B->C  当我要删除B的时候,就让A -> C @Override public E remove(int index) { //防止坐标越界 if(index < 0 || index >= size){ throw new IndexOutOfBoundsException("index： " + index + " size: " + size); } //获得要删除的元素Node         Node<E>node = node(index); //获得前一个结点         Node<E> pre = node.pre; //获得后一个结点         Node<E> next = node.next; if(pre == null){ //firest进行修改             first = next;             next.pre = null; }else{ //改变前一个结点的next             pre.next = next; } if(next == null){ //last进行修改             last = pre; }else{             next.pre = pre; }         size--; //返回老元素 return node.element; } @Override public int indexOf(E element) { //查找element元素是否存在,有返回索引,没有返回-1         Node N = first; int index = 0; //遍历 for(Node i = N; i != null; i = i.next){ if(element == i.element){ return index; }             index++; } return -1; } @Override public void clear() {         size = 0;         first = null;         last = null; } public String toString(){         Node N = first;         StringBuilder stringBuilder = new StringBuilder("["); boolean flag = false; //判断是否循环到了最后 for(Node i = N; i != null; i = i.next){ //说明已经到了最后一个元素 if(i.next == null) {                 flag = true; } //如果没到最后就加 逗号 if(flag == false){                 stringBuilder.append(i.element + ","); }else{ //到了最后就不加逗号                 stringBuilder.append(i.element); } }         stringBuilder.append("]"); return stringBuilder.toString(); } //内部Node节点类 private static class Node<E>{         Node<E> pre;         Node<E> next;         E element; public Node(Node next,E element){ this.next = next; this.element = element; } public Node(Node pre,Node next,E element){ this.pre = pre; this.next = next; this.element = element; } public Node() { } } }