数据结构--链表

一、链表简介：

内存.png

链表是由内存中一系列不相连的结构组成，每一个结构均含有表元素和next指针。优点是插入和删除比较方便(不需移动其他元素, 只需改变指针)，缺点是访问效率低，存储空间利用率高。

数组和链表比较：

数组静态分配内存，链表动态分配内存；数组在内存中连续，链表不连续；数组的元素在栈区，链表的元素在堆区；数组的查询效率比链表高；数组的插入和删除数据，需要其余数据移动，而链表只要在节点上插入和删除就可以；数组查询需要索引查询，链表查询需要遍历整个表。

二、链表分类：

单向链表

Snip20170615_7.png

循环链表

Snip20170615_8.png

双向循环链表

Snip20170615_9.png

三、以单向链表演示链表操作

//链表操作：插入，删除，遍历
class Haha {
    public static void main(String[] args){
        LinkList theList = new LinkList();
        theList.insertFirst(22,2);
        theList.insertFirst(33,3);
        theList.insertFirst(44,4);
        theList.insertFirst(55,5);
        theList.insertFirst(66,6);
        theList.insertFirst(77,7);

        theList.displayList();
        while (!theList.isEmpty()){
            JieDian aLink = theList.deleteFirst();
            System.out.print("Deleted ");
            aLink.displayJieDian();
            theList.displayList();
            System.out.println(" ");
        }
        theList.displayList();
    }
}

class JieDian{
    int iData;
    double dData;
    JieDian next;
    JieDian(int id,double dd){
        iData = id;
        dData = dd;
    }

    public void displayJieDian(){
        System.out.println("{"+iData+","+dData+"}");
    }
}

class LinkList{
    JieDian first;
    LinkList(){
        first = null;
    }
    public boolean isEmpty(){
        return (first == null);
    }
    public void insertFirst(int id,double dd){
        JieDian newJieDian = new JieDian(id,dd);
        newJieDian.next = first;
        first = newJieDian;
    }
    public JieDian deleteFirst(){
        JieDian temp = first;
        first = first.next;
        return temp;
    }
    public void displayList(){
        System.out.println("List(first -->last):");
        JieDian current = first;
        while(current != null){
            current.displayJieDian();
            current = current.next;
        }
    }
}

结果：

Snip20170616_1.png

常见问题：

1.判断一个给定的单链表是否有环？
2.环的入口
3.环的长度

Snip20170619_1.png Snip20170619_3.png

第一次相遇时：
slow走的长度S=AB+BC
fast走的长度2S=AB+BC+n*R
AB=n*R-BC
求入口：让两个指针同时分别从A、C出发，相遇点就是入口B
求环长：C点相遇之后，指针slow继续每次走1步，fast每次走2步。在下次相遇的时候fast比slow正好又多走了一圈，也就是多走的距离等于环长。

代码：

class Haha {
public static void main(String[] args){
        JieDian j1 = new JieDian(11,1);
        JieDian j2 = new JieDian(22,2);
        JieDian j3 = new JieDian(33,3);
        JieDian j4 = new JieDian(44,4);
        JieDian j5 = new JieDian(55,5);
        JieDian j6 = new JieDian(66,6);
        JieDian j7 = new JieDian(77,7);
        JieDian j8 = new JieDian(88,8);
        JieDian j9 = new JieDian(99,9);
        JieDian j10 = new JieDian(110,1);
        JieDian j11 = new JieDian(111,1);
        j1.next = j2;
        j2.next = j3;
        j3.next = j4;
        j4.next = j5;
        j5.next = j6;
        j6.next = j7;
        j7.next = j8;
        j8.next = j9;
        j9.next = j10;
        j10.next = j11;
        j11.next = j5;

        //环长
        int x = length(hasLoop(j1));
        System.out.println(x);
        //入口
        rukou(j1,hasLoop(j1)).displayJieDian();

    }
    //入口节点
    public static JieDian rukou(JieDian jd1,JieDian jd2){
        JieDian a1 = jd1;
        JieDian a2 = jd2;
        while (true){
            a1 = a1.next;
            a2 = a2.next;
            int d1 = a1.iData;
            int d2 = a2.iData;

            double t1 = a1.dData;
            double t2 = a2.dData;
            if(d1 == d2 && t1 == t2){
                return a1;
            }
        }
    }
    //环长
    public  static int length(JieDian jd){
        JieDian slow = jd;
        JieDian fast = jd;
        int length = 0;
        while(fast != null){
            length++;
            slow = slow.next;
            fast = fast.next.next;

            int d1 = slow.iData;
            int d2 = fast.iData;

            double t1 = slow.dData;
            double t2 = fast.dData;
            if(d1 == d2 && t1 == t2){
                return length;
            }
        }
        return 0;
    }
    //是否存在环，如果存在，返回相遇的结点
    public static JieDian hasLoop(JieDian jd){
        JieDian slow = jd;
        JieDian fast = jd;

        while(fast != null){
            slow = slow.next;
            fast = fast.next.next;
            if(fast == null){
                System.out.println("不存在环");
                return null;
            }
            int d1 = slow.iData;
            int d2 = fast.iData;

            double t1 = slow.dData;
            double t2 = fast.dData;
            if(d1 == d2 && t1 == t2){
                System.out.println("存在环");
                return slow;
            }
        }
        return null;
    }
}

class JieDian{
    int iData;
    double dData;
    JieDian next;
    JieDian(int id,double dd){
        iData = id;
        dData = dd;
    }

    public void displayJieDian(){
        System.out.println("{"+iData+","+dData+"}");
    }
}

运行结果：

Snip20170619_4.png