数据结构与算法(三)链表

定义

链表通过指针将一组零散的内存块串联在一起。其中,我们把内存块称为链表的“结点”。为了将所有的结点串起来,每个链表的结点除了存储数据之外,还需要记录链上的下一个结点的地址。

特点

  • 不需要连续的内存空间。
  • 有指针引用
  • 三种最常见的链表结构:单链表、双向链表和循环链表

图形

链表.jpeg

从单链表图中,可以发现,有两个结点是比较特殊的,它们分别是第一个结点和最后一个结点。我们一般把第一个结点叫作头结点,把最后一个结点叫作尾结点。
其中,头结点用来记录链表的基地址。有了它,我们就可以遍历得到整条链表。而尾结点特殊的地方是:指针不是指向下一个结点,而是指向一个空地址NULL,表示这是链表上最后一个结点。

  • 双向链表:双向链表有两个指针域,一个指向性上一个节点,一个指向下一个节点,头节点的上一个节点为NULL
  • 循环链表:循环链表是一种特殊的单链表。实际上,循环链表也很简单。它跟单链表唯一的区别就在尾结点。环链表的尾结点指针是指向链表的头结点。

数组和链表的区别

  1. 数组结构使用的是连续的内存空间,可以借助cpu缓存的机制,预读数组中的数据
  2. 链表在内存中并不是连续存储,所以对CPU缓存不友好,没办法有效预读。
  3. 数组的缺点是大小固定,一经声明就要占用整块连续内存空间。如果声明的数组过大,系统可能没有足够的连续内存空间分配给它,导致“内存不足(out of memory)”。如果声明的数组过小,则可能出现不够用的情况。
  4. 动态扩容:数组需再申请一个更大的内存空间,把原数组拷贝进去,非常费时。链表本身没有大小的限制,天然地支持动态扩容。
  5. 时间复杂度:数组的访问为O(1),修改为O(n);链表的访问为O(n),修改为O(1)

这里也不是绝对的,如果数组和链表都是在尾部或者头部进行操作,那数组和链表的访问和修改都是O(1),如栈和队列

手写一个LinkedList

public class MyLinkedList<E> implements MyList<E> {

    private int size;
    private Node<E> first;
    private Node<E> last;

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

    @Override
    public void add(E e) {
        Node<E> newNode = new Node<>(null, e, null);
        if (first == null) {
            first = newNode;
            last = newNode;
            size++;
            return;
        }
        last.next = newNode;
        newNode.pre = last;
        last = newNode;
        size++;
    }

    @Override
    public void add(E e, int index) {
        if (index < 0 || index > size) throw new IndexOutOfBoundsException();
        Node<E> newNode = new Node<>(null, e, null);
        if (index == size) {//加在末尾
            add(e);
            return;
        }
        Node<E> cur = node(index);
        newNode.next = cur;
        if (cur.pre == null) {//头
            cur.pre = newNode;
            first = newNode;
        } else {
            newNode.pre = cur.pre;
            cur.pre.next = newNode;
            cur.pre = newNode;
        }
        size++;
    }

    @Override
    public void remove(int index) {
        if (index < 0 || index > size) throw new IndexOutOfBoundsException();
        if (index == size) {
            last.pre.next = null;
            last = last.pre;
            size--;
            return;
        }
        Node<E> cur = node(index);
        if (cur.pre == null) {
            cur.next.pre = null;
            first = cur.next;
        } else {
            cur.pre.next = cur.next;
            cur.next.pre = cur.pre;
        }
        size--;
    }

    private Node<E> node(int index){
        Node<E> cur = null;
        if (index < (size >> 1)) {//插入位置小于链表的一半
            //从前遍历
            cur = first;
            for (int i = 0; i < index; i++) {
                cur = cur.next;
            }//index=3 插入在第四个位置 cur为第4个链表元素

        } else {
            //从后遍历
            cur = last;
            for (int i = size - 1; i > index; i--) {
                cur = cur.pre;
            }//index=3 插入在第四个位置 cur为第4个链表元素 size =5 last.index=4
        }
        return cur;
    }
    @Override
    public void remove(E e) {
        remove(indexOf(e));
    }

    @SuppressWarnings("unchecked")
    @Override
    public E get(int index) {
        return node(index).element;
    }

    @Override
    public Iterator<E> iterator() {
        return null;
    }

    @Override
    public int indexOf(E e) {
        Node<E> cur = first;
        for (int i = 0 ;i<size;i++){
            if(e.equals(cur.element)){
                return i;
            }
            cur = cur.next;
        }
        return -1;
    }

    private class Node<E> {
        private E element;
        private Node<E> pre;
        private Node<E> next;

        public Node(Node<E> pre, E element, Node<E> next) {
            this.pre = pre;
            this.element = element;
            this.next = next;
        }
    }
# 链表 

评论

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×