关于java:数据结构和算法-链表

4次阅读

共计 2307 个字符，预计需要花费 6 分钟才能阅读完成。

链表是线性表的一种。线性表就是字面意思，数据之间的关系被一条线所串联。

线性表又分为 地址空间间断的 和地址空间不间断 两种。

如数组就是地址空间间断线性表，他们在内存中是一块间断的数据块，块与块之间紧挨着，就好比 X 轴上的 [-1,0,1] 的关系一样。

而链表则是地址空间不间断的线性表，他们在内存中不是间断的块，而是扩散在各处，而后通过一条蜿蜒的线串起来了。

以下就是比拟形象的形容了。

地址空间间断线性表：

|😀 |😂|😆|🙃|😉|
地址空间不间断线性表

😀———->😂——->😆—>🙃————>🙃>😉

链表分为单链表和双链表。单链表就是只晓得下一个节点的地位(上图是单链表)，而双链表则能够晓得上一个和下一个节点的地位。

单链表上的每个节点蕴含两局部，一部分是链表节点上的数据，另一部分则是指向下一个节点的线（指针）。

双链表上的每个节点蕴含三局部，一部分是链表节点上的数据，一部分是指向下一个节点的线（指针），还有一部分则是指向上一个节点的线（指针）。

链表的基本操作

新增节点：在结尾、两头和开端
删除节点：在结尾、两头和结尾
查问节点：查问第 i 个地位的节点数据

public class LinkedList<E> implements List<E>, Queue<E>, Stack<E> {

    private int size = 0;

    private Node<E> head;
    private Node<E> tail;


    public LinkedList() {tail = head = null;}

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

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

    @Override
    public boolean add(E e) {return offer(e);
    }

    @Override
    public boolean remove(E e) {
        Node<E> tmp = head;
        int idx = 0;
        while (tmp != null) {if (tmp.e.equals(e)) {remove(idx);
                return true;
            }
            idx++;
            tmp = tmp.next;
        }
        return false;
    }

    @Override
    public boolean contains(E e) {
        Node<E> tmp = head;
        while (tmp != null) {if (tmp.e.equals(e)) {return true;}
            tmp = tmp.next;
        }
        return false;
    }

    @Override
    public E get(int i) {if (i > size) {throw new IndexOutOfBoundsException("Index i" + i + "out of range" + size);
        }
        if (i == 0) {return head.e;}
        if (i == size - 1) {return tail.e;}
        Node<E> tmp = head;
        for (int j = 0; j < i; j++) {tmp = tmp.next;}
        return tmp.e;
    }

    @Override
    public E remove(int i) {if (i >= size) {throw new IndexOutOfBoundsException("Index i" + i + "out of range" + size);
        }
        if (i == 0) {return poll();
        }
        if (i == size - 1) {return pop();
        }
        Node<E> tmp = head;
        for (int j = 0; j < i; j++) {tmp = tmp.next;}
        E e = tmp.next.e;
        tmp.next.next.prev = tmp;
        tmp.next = tmp.next.next;
        return e;
    }

    @Override
    public boolean add(E e, int i) {if (i > size) {throw new IndexOutOfBoundsException("Index i" + i + "out of range" + size);
        }
        Node<E> node = new Node<>(e);
        if (i == size) {return offer(e);
        }
        if (i == 0) {
            node.next = head;
            node.prev = null;
            head = node;
        } else {
            Node<E> tmp = head;
            for (int j = 0; j <= i; j++) {tmp = tmp.next;}
            tmp.next = node;
            node.prev = tmp;
        }
        size++;
        return false;
    }

    @Override
    public String toString() {StringBuilder sb = new StringBuilder();
        sb.append("LinkedList: {");
        Node<E> node = head;
        while (node != null) {sb.append(node.e).append("<->");
            node = node.next;
        }
        sb.append("null}");
        return sb.toString();}

    private static class Node<E> {

        E e;

        Node<E> next;
        Node<E> prev;

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

}