Java数据结构算法

链表
应用

链表

　　“数组”作为数据存储结构有一定的缺陷

无序数组——搜索效率是低效的
有序数组——插入效率低

　　不管在哪种数组中删除效率都很低，创建数组后，大小不可改变

线性数据结构

为什么链表很重要？

最简单的动态数据结构
更深入的理解引用（或者指针）
更深入的理解递归
辅助组成其他的数据结构（图结构、哈希表、队列）

链表 LinkedList

　　数据储存在“节点（Node）”中，一个链节点是某个类的对象

　　优点：真正的动态，不需要处理固定容量的问题（不用像数组new出来一片空间）

　　缺点：不能随机访问（数组开辟的空间在内存上是连续的，可以通过下标计算出内存地址进行随机访问，而链表必须是顺序访问，由于依靠next一层一层连接，在计算机的底层，每一个节点对应的内存地址不同）

数组和链表的对比

　　数组：最好用于索引有语意的情况（user[1]）

　　优点：快速查询

　　数组：最好不用于索引有语意的情况

　　链表：动态

应用

1、在链表头添加元素

　　在数组中，在最后面添加元素是最方便的，因为有size在跟踪数组的最后一个元素

　　但是链表恰恰相反，链表头添加元素，因为有head头结点，没有跟踪最后一个元素的结点

public class LinkedList<E>{

    private class Node{
        public E e;
        public Node next;

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

        public Node(E e){
            this(e,null);
        }

        public Node(){
            this(null,null);
        }
    }

    private Node head;
    private int size;

    public LinkedList(){
        head=null;
        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;

        //head=new Node(e);相当于上面三行
        size++;
    }
}

View Code

2、在链表中间（末尾）添加元素

　　在搜索为2的位置插入元素

　　关键：找到添加结点的前一个节点

　　注意：如插入到索引为0的节点后面，头结点没有前驱节点

  //在链表中间添加元素
    public void add(int index,E e){
        //判断索引的和发现
        if(index<0||index>size){
            throw new IllegalArgumentException("add failed,illegal index");
        }
        //如果在链表头添加，由于链表头没有前驱节点，需特殊处理
        if(index==0){
            addFirst(e);
        }else{
            Node pre=head;
            for (int i = 0; i <index-1 ; i++) {
                //一直将前驱节点向前移，直到找到index位置的节点
                pre=pre.next;
                Node node=new Node(e);
                node.next=pre.next;
                pre.next=node;

                //pre.next=new Node(e,pre.next);相当于上面三行
                size++;
            }
        }
    }

    //在链表末尾添加元素
    public void addLast(E e){
        add(size,e);
    }

View Code

3、为链表设置虚拟头结点

　　由于头结点没有前驱节点，在链表头结点和其他位置插入元素，会有所不同

　　因此构建一个虚拟头结点为null，就不需要对头结点进行特殊处理，只需要找到待添加元素的前一个节点

    //在链表中间添加元素
    public void add(int index,E e){
        //判断索引的和发现
        if(index<0||index>size){
            throw new IllegalArgumentException("add failed,illegal index");
        }
        //如果在链表头添加，由于链表头没有前驱节点，需特殊处理
            Node pre=dummyHead;
            for (int i = 0; i <index; i++) {
                //一直将前驱节点向前移，直到找到index位置的节点
                pre=pre.next;
                Node node=new Node(e);
                node.next=pre.next;
                pre.next=node;

                //pre.next=new Node(e,pre.next);相当于上面三行
                size++;
            }
    }

    //在链表末尾添加元素
    public void addLast(E e){
        add(size,e);
    }

    //在链表头结点添加元素
    public void addFirst(E e){
        add(0,e);
    }

View Code

4、链表

    //获得链表的第index(0-base)个位置的元素
    public E get(int index){
        //判断索引的合法性
        if(index<0||index>size){
            throw new IllegalArgumentException("add failed,illegal 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);
    }

View Code