线性结构--链表

之前写的几种数据结构--数组.栈.队列等都算静态数据结构,就算是实现了动态扩容其底层也是通过静态数组来完成的.本篇链表才是真正的动态数据结构,也是最简单的动态数据结构

属性:

①：相邻元素之间通过指针连接。
②：最后一个元素的后继指针为NULL。
③：链表的空间能够按需分配。
④：没有内存空间的浪费。

结构:

• 链表数据存储在内部节点(Node)中
• Node中包含了该节点的数据和它的下一个节点

class Node{
  E e;
  Node next;
}

代码实现:

添加插入数据:

public class LinkList<E> {
    private class Node<E>{
        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 int size;
    private Node head;

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

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

    // 在链表的index(0-based)位置添加新的元素e
    // 在链表中不是一个常用的操作，练习用：）
    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 prve = head;
            for (int i = 0; i < index; i++) {
                prve = prve.next;
            }
//            Node node = new Node(e);
//            node.next = prve.next;
//            prve.next = node;
//            该行代码等效于上面3行
            prve.next = new Node(e,prve.next);
            size++;
        }
    }

    // 在链表头添加新的元素e
    public void addFirst(E e){
//        第一种写法
//        Node node = new Node(e);
//        node.next = head;
//        head = node;


//        第二种
        head = new Node(e,head);
        size++;
    }

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

• addFirst函数--添加一个新的头结点，这样原来的头结点就往后移一位--也就是新节点的的next等于之前的头结点
• 实现代码中add函数稍微需要理解一下,下面放张图来帮助理解:

插入元素

使用虚拟头节点:

从上面的代码中可以看到头结点是一个比较特殊的节点,于其他节点不同由于它是第一个节点所以没有其他节点来指向它,这样就造成了对于头结点需要一些逻辑判断上的操作
而通过虚拟头结点我们可以规避的这些,其主要实现就是创建一个结点它不需要存储数据,唯一目的就是通过它来指向结点--这个被指向的结点就是实际的头结点:

虚拟头结点

    private Node dummyHead;

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

    // 在链表的index(0-based)位置添加新的元素e
    // 在链表中不是一个常用的操作，练习用：）
    public void add(int index, E e) {
        if (index < 0 || index > size)
            throw new IllegalArgumentException("Add failed. Illegal index.");

        Node prve = dummyHead;
        for (int i = 0; i < index-1; i++) {
            prve = prve.next;
        }
        prve.next = new Node(e, prve.next);
        size++;
    }

链表的set和get方法

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

    public Boolean contain(E e){
        Node cur = dummyHead.next;
        while (cur.next != null) {
            if (cur.e==e) {
                return true;
            }
            cur = cur.next;
        }
        return false;
    }

    public void set(int index,E e){
        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;
        }

        cur.e = e;
    }


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

测试以及结果:

    public static void main(String[] args) {
        LinkedList<Integer> linkedList = new LinkedList<>();
        for(int i = 0 ; i < 5 ; i ++){
            linkedList.addFirst(i);
            System.out.println(linkedList);
        }

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

[0]
[1, 0]
[2, 1, 0]
[3, 2, 1, 0]
[4, 3, 2, 1, 0]
[4, 3, 666, 2, 1, 0]

Process finished with exit code 0

删除元素:

    // 在链表的index(0-based)位置删除元素e
    // 在链表中不是一个常用的操作，练习用：）
  public E remove(int index){
        if (index < 0 || index > size)
            throw new IllegalArgumentException("Add failed. Illegal index.");
        Node pre= dummyHead.next;
        for (int i = 0; i < index; i++) {
            pre= pre.next;
        }
        Node delNode= pre.next；
        pre.next = delNode.next;
        delNode.next= null;
        size--;
        return delNode.e;
  }

时间复杂度分析:

• 添加操作：O(n)
  addFirst() O(1)
  addLast() O(n)
  add(index,e) O(n/2)=O(n)
• 删除操作：O(n)
  removeFirst() O(1)
  removeLast() O(n)
  remove(index) O(n/2)=O(n)
• 查找操作：O(n)
  get(index) O(n)
  contain(e) O(n)

从上面时间复杂度分析可以看出链表的增、删、改（这里没有）、查的时间复杂度都是O(n),相对于数组结构并没有什么优势，但细心的同学可以看出，当对链表头进行操作时它的时间复杂度为O(1)--相当的高效。聪明的同学就应该想到了，栈这种数据结构非常就适合使用链表来实现，下一篇就通过链表来实现栈这个数据结构。