美文网首页
数据结构-链表

数据结构-链表

作者: 听你讲故事啊 | 来源:发表于2019-03-29 09:21 被阅读0次

    前面创建的动态数组, 栈和队列底层都是依托于静态数组的,靠resize来解决容量问题.而链表是真正的动态数据结构.

    创建一个链表

    链表的数据存储在节点(Node)中

    class Node{
    E e;
    Node next;
}

    最后一个节点的next指向null,链表相较于数组来说,丧失了随机访问的能力,但是却是真正的动态,不需要处理固定容量的问题

    链表节点

    新建一个LinkedList类

    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);
        }

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

}

    添加元素

    public class LinkedList<E> {
    
    private class Node{
        ...
    }

    // 这里使用虚拟头结点, 接下来的增删改查操作将会方便很多
    private Node dummyHead;
    private int size;

    public LinkedList(){
        dummyHead = new Node();
        size = 0;
    }

    // 获取链表中的元素个数
    public int getSize(){
        return size;
    }

    // 返回链表是否为空
    public boolean isEmpty(){
        return size == 0;
    }

    // 在链表的index(0-based)位置添加新的元素e
    public void add(int index, E e){

        if(index < 0 || index > size)
            throw new IllegalArgumentException("Add failed. Illegal index.");

        Node prev = dummyHead;
        for(int i = 0 ; i < index ; i ++)
            prev = prev.next;

        prev.next = new Node(e, prev.next);
        //  等价
        //  Node node = new Node(e);
        //  node.next = prev.next;
        //  prev.next = node;
        size ++;
    }

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

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

    修改元素

        // 修改链表的第index(0-based)个位置的元素为e
    public void set(int index, E e){
        if(index < 0 || index >= size)
            throw new IllegalArgumentException("Set failed. Illegal index.");

        Node cur = dummyHead.next;
        for(int i = 0 ; i < index ; i ++)
            cur = cur.next;
        cur.e = e;
    }

    重写toString方法进行测试

        @Override
    public String toString() {
        StringBuilder res = new StringBuilder();

//        Node cur = dummyHead.next;
//        while(cur != null){
//            res.append(cur + "->");
//            cur = cur.next;
//        }
        for (Node cur = dummyHead.next; cur != null; cur = cur.next)
            res.append(cur + "->");
        res.append("NULL");

        return res.toString();
    }

    查询元素

       // 获得链表的第index(0-based)个位置的元素
    public E get(int index){

        if(index < 0 || index >= size)
            throw new IllegalArgumentException("Get 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);
    }

    // 查找链表中是否有元素e
    public boolean contains(E e){
        Node cur = dummyHead.next;
        while(cur != null){
            if(cur.e.equals(e))
                return true;
            cur = cur.next;
        }
        return false;
    }

    删除元素

        // 从链表中删除index(0-based)位置的元素, 返回删除的元素
    public E remove(int index){
        if(index < 0 || index >= size)
            throw new IllegalArgumentException("Remove failed. Index is illegal.");

        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 --;

        return retNode.e;
    }

    // 从链表中删除第一个元素, 返回删除的元素
    public E removeFirst(){
        return remove(0);
    }

    // 从链表中删除最后一个元素, 返回删除的元素
    public E removeLast(){
        return remove(size - 1);
    }

    // 从链表中删除元素e
    public void removeElement(E e){

        Node prev = dummyHead;
        while(prev.next != null){
            if(prev.next.e.equals(e))
                break;
            prev = prev.next;
        }

        if(prev.next != null){
            Node delNode = prev.next;
            prev.next = delNode.next;
            delNode.next = null;
            size --;
        }
    }

    编写main函数进行测试

    import java.util.Random;

public class Main {

    public static void main(String[] args) {

        LinkedList<Integer> linkedList = new LinkedList<>();
        for (int i = 0; i < 5; i++) {
            linkedList.addFirst(new Random().nextInt(10));
            System.out.println(linkedList);
        }

        linkedList.add(2, 666);
        System.out.println(linkedList);

        linkedList.remove(2);
        System.out.println(linkedList);

        linkedList.removeFirst();
        System.out.println(linkedList);

        linkedList.removeLast();
        System.out.println(linkedList);
    }
}

    结果

    2->NULL
5->2->NULL
3->5->2->NULL
8->3->5->2->NULL
6->8->3->5->2->NULL
6->8->666->3->5->2->NULL
6->8->3->5->2->NULL
8->3->5->2->NULL
8->3->5->NULL

    时间复杂度分析

    • 添加操作

      • addLast(e) O(n)
      • addFirst(e) O(1)
      • add(index, e) O(n/2) = O(n)

    • 删除操作

      • removeLast() O(n)
      • removeFirst() O(1)
      • remove(index) O(n/2) = O(n)

    • 修改操作

      • set(index, e) O(n)

    • 查找操作

      • get(index) O(n)
      • contains O(n)

    • 如果只对链表头进行操作,复杂度是O(1)

    使用链表实现栈

    直接使用之前创建的栈接口即可
    因为栈只能从一端进行操作,这里使用链表头作为栈顶
    创建LinkedListStack类, 实现栈的接口方法, 并进行简单测试

    public class LinkedListStack<E> implements Stack<E> {
    private LinkedList<E> list;

    public LinkedListStack() {
        list = new LinkedList<>();
    }

    @Override
    public int getSize() {
        return list.getSize();
    }

    @Override
    public boolean isEmpty() {
        return list.isEmpty();
    }

    @Override
    public void push(E e) {
        list.addFirst(e);
    }

    @Override
    public E pop() {
        return list.removeFirst();
    }

    @Override
    public E peek() {
        return list.getFirst();
    }

    @Override
    public String toString() {
        StringBuilder res = new StringBuilder();
        res.append("Stack: top ");
        res.append(list);
        return res.toString();
    }

    public static void main(String[] args) {

        LinkedListStack<Integer> stack = new LinkedListStack<>();

        for (int i = 0; i < 5; i++) {
            stack.push(i);
            System.out.println(stack);
        }

        stack.pop();
        System.out.println(stack);
    }
}

    运行结果

    Stack: top 0->NULL
Stack: top 1->0->NULL
Stack: top 2->1->0->NULL
Stack: top 3->2->1->0->NULL
Stack: top 4->3->2->1->0->NULL
Stack: top 3->2->1->0->NULL

    链表栈和数组栈对比

    编写一个main函数进行测试

    import java.util.Random;

public class Main {

    // 测试使用stack运行opCount个push和pop操作所需要的时间，单位：秒
    private static double testStack(Stack<Integer> stack, int opCount) {

        long startTime = System.nanoTime();

        Random random = new Random();
        for (int i = 0; i < opCount; i++)
            stack.push(random.nextInt(Integer.MAX_VALUE));
        for (int i = 0; i < opCount; i++)
            stack.pop();

        long endTime = System.nanoTime();

        return (endTime - startTime) / 1000000000.0;
    }

    public static void main(String[] args) {

        int opCount = 50000000;

        ArrayStack<Integer> arrayStack = new ArrayStack<>();
        double time1 = testStack(arrayStack, opCount);
        System.out.println("ArrayStack, time: " + time1 + " s");

        LinkedListStack<Integer> linkedListStack = new LinkedListStack<>();
        double time2 = testStack(linkedListStack, opCount);
        System.out.println("LinkedListStack, time: " + time2 + " s");
    }
}

    ArrayStack, time: 7.5600347 s
LinkedListStack, time: 14.0287178 s

    两者的时间复杂度是一样的, 但是运行的时间却是不一样的
    其实这个时间比较很复杂，jdk, LinkedListStack中包含更多的new操作, 机器性能等等

    使用链表实现队列

    在实现队列前,需要对链表进行改造
    在链表头进行操作时时间复杂度是O(1)级别的,是因为对头节点进行了标记,如果对链表尾节点也进行标记,这样在链表尾进行添加操作时也可以通过标记直接添加, 时间复杂度也是O(1)级别的

    但是这样的话在链表尾部删除元素时时间复杂度依然是O(n)级别的, 根据队列的性质, 我们可以从链表尾部添加元素(入队), 在链表头部进行删除元素(出队), 这样时间复杂度都是O(1)级别的了

    创建LinkedListQueue类, 实现之前的Queue接口, 进行简单的测试

    public class LinkedListQueue<E> implements Queue<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);
        }

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

    private Node head, tail;
    private int size;

    public LinkedListQueue(){
        head = null;
        tail = null;
        size = 0;
    }

    @Override
    public int getSize(){
        return size;
    }

    @Override
    public boolean isEmpty(){
        return size == 0;
    }

    @Override
    public void enqueue(E e){
        if(tail == null){
            tail = new Node(e);
            head = tail;
        }
        else{
            tail.next = new Node(e);
            tail = tail.next;
        }
        size ++;
    }

    @Override
    public E dequeue(){
        if(isEmpty())
            throw new IllegalArgumentException("Cannot dequeue from an empty queue.");

        Node retNode = head;
        head = head.next;
        retNode.next = null;
        if(head == null)
            tail = null;
        size --;
        return retNode.e;
    }

    @Override
    public E getFront(){
        if(isEmpty())
            throw new IllegalArgumentException("Queue is empty.");
        return head.e;
    }

    @Override
    public String toString(){
        StringBuilder res = new StringBuilder();
        res.append("Queue: front ");

        Node cur = head;
        while(cur != null) {
            res.append(cur + "->");
            cur = cur.next;
        }
        res.append("NULL tail");
        return res.toString();
    }

    public static void main(String[] args){

        LinkedListQueue<Integer> queue = new LinkedListQueue<>();
        for(int i = 0 ; i < 10 ; i ++){
            queue.enqueue(i);
            System.out.println(queue);

            if(i % 3 == 2){
                queue.dequeue();
                System.out.println(queue);
            }
        }
    }
}

    运行结果

    Queue: front 0->NULL tail
Queue: front 0->1->NULL tail
Queue: front 0->1->2->NULL tail
Queue: front 1->2->NULL tail
Queue: front 1->2->3->NULL tail
Queue: front 1->2->3->4->NULL tail
Queue: front 1->2->3->4->5->NULL tail
Queue: front 2->3->4->5->NULL tail
Queue: front 2->3->4->5->6->NULL tail
Queue: front 2->3->4->5->6->7->NULL tail
Queue: front 2->3->4->5->6->7->8->NULL tail
Queue: front 3->4->5->6->7->8->NULL tail
Queue: front 3->4->5->6->7->8->9->NULL tail

    三种队列对比

    import java.util.Random;

public class Main {

    // 测试使用q运行opCount个enqueueu和dequeue操作所需要的时间，单位：秒
    private static double testQueue(Queue<Integer> q, int opCount){

        long startTime = System.nanoTime();

        Random random = new Random();
        for(int i = 0 ; i < opCount ; i ++)
            q.enqueue(random.nextInt(Integer.MAX_VALUE));
        for(int i = 0 ; i < opCount ; i ++)
            q.dequeue();

        long endTime = System.nanoTime();

        return (endTime - startTime) / 1000000000.0;
    }

    public static void main(String[] args) {

        int opCount = 100000;

        ArrayQueue<Integer> arrayQueue = new ArrayQueue<>();
        double time1 = testQueue(arrayQueue, opCount);
        System.out.println("ArrayQueue, time: " + time1 + " s");

        LoopQueue<Integer> loopQueue = new LoopQueue<>();
        double time2 = testQueue(loopQueue, opCount);
        System.out.println("LoopQueue, time: " + time2 + " s");

        LinkedListQueue<Integer> linkedListQueue = new LinkedListQueue<>();
        double time3 = testQueue(linkedListQueue, opCount);
        System.out.println("LinkedListQueue, time: " + time3 + " s");
    }
}

    运行结果

    ArrayQueue, time: 76.0986852 s
LoopQueue, time: 0.0206508 s
LinkedListQueue, time: 0.0129043 s

    主要差异:
    ArrayQueue出队的时间复杂度是O(n)级别的,再加上外层的循环就是O(n^2)级别的了,所以对于ArrayQueue来说,testQueue方法的时间复杂度是O(n^2)级别的;
    LoopQueue出队的时间复杂度是O(1)级别的, 再加上外层的循环就是O(n)级别的了,所以对于LoopQueue来说,testQueue方法的时间复杂度是O(n)级别的;
    LinkedListQueue队列出队的时间复杂度是O(1)级别的, 再加上外层的循环就是O(n)级别的了,所以对于LinkedListQueue来说,testQueue方法的时间复杂度是也是O(n)级别的;

    完整代码

    相关文章

      网友评论

          本文标题：数据结构-链表

          本文链接：https://www.haomeiwen.com/subject/ioykbqtx.html

          延伸阅读

          深度阅读

          • 您也可以注册成为美文阅读网的作者，发表您的原创作品、分享您的心情！

          栏目导航

          热点阅读

          关于我们|服务条款|联系我们|数据结构-链表|投稿指南|网站地图|RSS订阅|排版工具|手机版

          提供经典美文摘抄,优美散文欣赏,现代诗歌精选,短篇小说,心情随笔,表白情书范文,故事会在线阅读欣赏

          Copyright © 2014-2023 Haomeiwen.com All Rights Reserved. 好美文阅读网 版权所有

          备案信息：桂公网安备 45052102000051号 · 桂ICP备13007215号-3

          本站所收录作品、热点评论等信息部分来源互联网，目的只是为了系统归纳学习和传递资讯

          所有作品版权归原创作者所有，与本站立场无关，如不慎侵犯了你的权益，请联系我们告知，我们将做删除处理！