数据结构-基础线性表结构

顺序结构

基于数组实现的线性表，在进行插入和删除时由于需要移动元素，所以时间复杂度都是O(1)，但能够支持O(1)时间复杂度的随机查找，例如在列表[1,5,6,3,2]的index=1的位置超如10，就需要把[5,6,3,2]以此向后移动，而如果要将1这个元素删除，就需要把[5,6,3,2]这几个元素以此向前移动。

public class EArrayList {

    private E[] data;
    private int size;

    public EArrayList() {
        this(16);
    }

    public EArrayList(int capacity) {
        data = (E[])new Object[capacity];
        size = 0;
    }

    
    public void add(E e) {
        add(e, size);
    }
    //在任意位置添加元素e
    public void add(E e, int index) {
        if (index < 0 || index > size) {
            throw new IllegalArgumentException("index error");
        }
        if (size == data.length) {
            growUp(data.length * 2);
        }
        //将index后面的位置的数据向后移动一个位置
        for (int i = size - 1;i >= index;i --) {
            data[i + 1] = data[i];
        }
        data[index] = e;
        size ++;
    }

    //扩容到newCapacity
    private void growUp(int newCapacity) {
        System.out.println("EArrayList growing up..");
        E[] newData = (E[])new Object[newCapacity];
        System.arraycopy(data, 0, newData, 0, size);
        data = newData;
    }

    
    public E remove(int index) {
        if (index < 0 || index >= size) {
            throw new IllegalArgumentException("index error");
        }
        E removeValue = data[index];
        //将index之后的元素向前移动一个位置
        for (int i = index;i < size -  1;i ++) {
            data[i] = data[i + 1];
        }
        size --;
        return removeValue;
    }

    
    public E set(E e, int index) {
        if (index < 0 || index >= size) {
            throw new IllegalArgumentException("index error");
        }
        E oldValue = data[index];
        data[index] = e;
        return oldValue;
    }

    
    public E get(int index) {
        if (index < 0 || index >= size) {
            throw new IllegalArgumentException("index error");
        }
        return data[index];
    }

    public int getSize() {
        return size;
    }

    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder();
        sb.append("[ ");
        for (int i = 0;i < size;i ++) {
            sb.append(data[i]);
            if (i != size -1) {
                sb.append(",");
            }
        }
        sb.append(" ]");
        return sb.toString();
    }

    public static void main(String[] args) {
        EArrayList list = new EArrayList<>(2);
        list.add(1);
        list.add(2);
        list.add(3);
        list.add(4);
        //[ 1,2,3,4 ]
        System.out.println(list);
        list.add(10, 2);
        //[ 1,2,10,3,4 ]
        System.out.println(list);
        list.remove(1);
        //[ 1,10,3,4 ]
        System.out.println(list);
    }
}

链式结构

链式结构相比于数组结构的优势在于不用一次性申请连续的存储空间，可以离散的数据存储在不同的存储区域中，另外链式结构中插入和删除操作的时间复杂度为O(1)，但随机查找的时间复杂度为O(n)，如果能够持有链表中某个节点的引用那么插入和删除操作都是很快的，但更多的时候需要先遍历到指定的节点，在这种场景下整体来说链表的效率就不然数组，但如果是在链表的两端对元素进行操作，那就能很好的体现链式结构的优势了，比如用链表实现栈、队列等，就非常合适。

单链表

单向链表，不存在环形结构，通过一个dummyHead来统一添加数据的逻辑。

插入：

Node node = new Node(e);

node.next = prev.next;

prev.next = node;



删除：

Node delNode = prev.next;

prev.next = delNode.next;

delNode.next = null;

完整实现如下：

public class ESingleLinkedList {

    private Node dummyHead;
    private int size;

    public ESingleLinkedList() {
        dummyHead = new Node<>();
        size = 0;
    }

    
    public void add(E e) {
        add(e, size);
    }

    
    public void add(E e, int index) {
        if (index < 0 || index > size) {
            throw new IllegalArgumentException("index error.");
        }
        //找到index - 1的位置
        Node prev = getPrevNode(index);

        Node newNode = new Node<>(e);
        newNode.next = prev.next;
        prev.next = newNode;
        size ++;
    }

    
    public E set(E e, int index) {
        Node node = getNode(index);
        E retValue = node.data;
        node.data = e;
        return retValue;
    }

    
    public E get(int index) {
        Node node = getNode(index);
        return node.data;
    }

    
    public E remove(int index) {
        if (index < 0 || index >= size) {
            throw new IllegalArgumentException("index error.");
        }
        Node prev = getPrevNode(index);
        Node delNode = prev.next;
        prev.next = delNode.next;
        delNode.next = null;
        size --;
        return delNode.data;
    }

    //获取指定位置上的Node
    private Node getNode(int index) {
        if (index < 0 || index >= size) {
            throw new IllegalArgumentException("index error.");
        }
        Node cur = dummyHead;
        for (int i = 0;i <= index;i ++) {
            cur = cur.next;
        }
        return cur;
    }

    //获取指定位置的前一个Node
    private Node getPrevNode(int index) {
        if (index < 0 || index > size) {
            throw new IllegalArgumentException("index error.");
        }
        Node pre = dummyHead;
        for (int i = 0;i < index;i ++) {
            pre = pre.next;
        }
        return pre;
    }


    public int getSize() {
        return size;
    }

    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder();
        sb.append("[ ");
        Node cur = dummyHead.next;
        while (cur != null) {
            sb.append(cur.data);
            if (cur.next != null) {
                sb.append(",");
            }
            cur = cur.next;
        }
        sb.append(" ]");
        return sb.toString();
    }

    private static class Node {
        E data;
        Node next;

        public Node() {
            this(null);
        }

        public Node(E data) {
            this(data, null);
        }
        public Node(E data, Node next) {
            this.data = data;
            this.next = next;
        }
    }

    public static void main(String[] args) {
        ESingleLinkedList list = new ESingleLinkedList<>();
        list.add(1);
        list.add(2);
        list.add(3);
        //[ 1,2,3 ]
        System.out.println(list);
        list.add(10, 1);
        //[ 1,10,2,3 ]
        System.out.println(list);
        //2
        System.out.println(list.remove(2));
        //[ 1,10,3 ]
        System.out.println(list);
        list.set(40, 2);
        //[ 1,10,40 ]
        System.out.println(list);
    }
}

双链表

双链表相比于单链表而言，多了一个前向指针，操作基本上和单向链表一致，只是需要加入对前向指针的操作。

插入：
Node node = new Node(e);
node.next = pre.next;
node.prev = prev;
prev.next.prev = node;
prev.next = node;

删除：
Node delNode = prev.next;
prev.next = delNode.next;
delNode.next.prev = pre;
delNode.next = delNode.prev = null;

完整实现如下：

public class EDoubleLinkedList {

    private Node dummyHead;
    private int size;


    public EDoubleLinkedList() {
        this.dummyHead = new Node<>();
        this.size = 0;
    }

    
    public void add(E e) {
        add(e, size);
    }

    
    public void add(E e, int index) {
        if (index < 0 || index > size) {
            throw new IllegalArgumentException("index error");
        }
        Node prev = getPrevNode(index);
        Node newNode = new Node<>(e);
        newNode.next = prev.next;
        newNode.prev = prev;
        if (prev.next != null)
            prev.next.prev = newNode;
        prev.next = newNode;
        size ++;
    }

    
    public E set(E e, int index) {
        if (index < 0 || index >= size) {
            throw new IllegalArgumentException("index error");
        }
        Node node = getNode(index);
        E retValue = node.data;
        node.data = e;
        return retValue;
    }

    
    public E get(int index) {
        if (index < 0 || index >= size) {
            throw new IllegalArgumentException("index error");
        }
        Node node = getNode(index);
        return node.data;
    }

    
    public E remove(int index) {
        if (index < 0 || index >= size) {
            throw new IllegalArgumentException("index error");
        }

        Node prev = getPrevNode(index);
        Node delNode = prev.next;
        prev.next = delNode.next;
        if (delNode.next != null)
            delNode.next.prev = prev;
        delNode.next = delNode.prev = null;
        size --;
        return delNode.data;
    }

    //获取index位置上的node
    private Node getNode(int index) {
        Node cur = dummyHead;
        int i = 0;
        while (i <= index) {
            cur = cur.next;
            i ++;
        }
        return cur;
    }

    //获取index的前一个位置的node
    private Node getPrevNode(int index) {
        Node cur = dummyHead;
        int i = 0;
        while (i < index) {
            cur = cur.next;
            i ++;
        }
        return cur;
    }

    public int getSize() {
        return size;
    }

    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder();
        sb.append("[ ");
        Node cur = dummyHead.next;
        for (int i = 0;i < size;i ++) {
            sb.append(cur.data);
            if (i != size -1) {
                sb.append(",");
            }
            cur = cur.next;
        }
        sb.append(" ]");
        return sb.toString();
    }

    private class Node {
        E data;
        Node prev;
        Node next;
        public Node() {
            this(null);
        }
        public Node(E data) {
            this(data, null,null);
        }
        public Node(E data, Node prev, Node next) {
            this.data = data;
            this.prev = prev;
            this.next = next;
        }
    }

    public static void main(String[] args) {
        EDoubleLinkedList list = new EDoubleLinkedList<>();
        list.add(1);
        list.add(2);
        list.add(3);
        list.add(4);
        //[ 1,2,3,4 ]
        System.out.println(list);
        list.add(10, 2);
        //[ 1,2,10,3,4 ]
        System.out.println(list);
        list.set(100, 0);
        //[ 100,2,10,3,4 ]
        System.out.println(list);
        //4
        System.out.println(list.remove(4));
        //[ 100,2,10,3 ]
        System.out.println(list);
    }

}

循环链表

用单链表实现一个循环链表，循环链表与单链表的区别在于尾节点的next指针指向头节点。为了实现在头节点和尾节点添加节点时都有O(1)的性能，定义一个last指针指向尾节点。

public class ERecycleSingleLinkedList {

    private Node last;
    private int size;

    public ERecycleSingleLinkedList() {
        this.size = 0;
    }

    
    public void addLast(E e) {
        if (last == null) {
            addToEmpty(e);
            return;
        }

        Node newNode = new Node<>(e);
        newNode.next = last.next;
        last.next = newNode;
        last = newNode;
        size ++;
    }

    
    public void addFirst(E e) {
        if (last == null) {
            addToEmpty(e);
            return;
        }
        Node newNode = new Node<>(e);
        newNode.next = last.next;
        last.next = newNode;
        //不对last指针进行后移
        size ++;
    }

    
    public void add(E e, int index) {
        if (index < 0 || index > size) {
            throw new IllegalArgumentException("index error.");
        }
        if (last == null) {
            addToEmpty(e);
            return;
        }

        //找到index之前的那个位置
        Node prev = getPrevNode(index);
        Node newNode = new Node<>(e);
        newNode.next = prev.next;
        prev.next = newNode;
        size ++;
    }

    
    public void remove(E data) {
        //如果链表为空，直接范围
        if (size == 0) {
            return;
        }
        Node head = last.next;
        Node cur = last.next;
        Node pre = last;

        //如果链表只有一个节点，单独处理
        if (data.equals(cur.data)
                && last == head) {
            last = null;
            size --;
            return;
        }

        //从头开始遍历整个节点
        for (int i = 0;i < size;i ++ ) {
            //如果找到了待删除的节点
            if (cur.data.equals(data)) {
                Node delNode = cur;
                pre.next = cur.next;
                //无用，让理解上更连贯
                cur = cur.next;
                delNode.next = null;
                size --;
                //如果此时pre.next = 头结点，说明删除的是尾节点，需要更新last指针为pre
                if (pre.next == head) {
                    last = pre;
                }
                return;
            }
            pre = cur;
            cur = cur.next;
        }
    }

    private Node getPrevNode(int index) {
        Node cur = last;
        for (int i = 0;i < index;i ++) {
            cur = cur.next;
        }
        return cur;
    }

    private void addToEmpty(E e) {
        Node newNode = new Node<>(e);
        newNode.next = newNode;
        size ++;
        last = newNode;
    }

    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder();
        sb.append("[ ");
        if (size > 0) {
            Node cur = last.next;
            for (int i = 0; i < size ; i++) {
                sb.append(cur.data);
                if (i != size - 1) {
                    sb.append(",");
                }
                cur = cur.next;
            }
        }
        sb.append(" ]");
        return sb.toString();
    }

    private static class Node {

        E data;
        Node next;

        public Node() {
            this(null);
        }
        public Node(E data) {
            this(data, null);
        }
        public Node(E data, Node next) {
            this.data = data;
            this.next = next;
        }
    }

    public static void main(String[] args) {
        ERecycleSingleLinkedList list = new ERecycleSingleLinkedList<>();
        list.addLast(1);
        list.addLast(2);
        list.addLast(3);
        System.out.println(list);
        list.add(4, 1);
        System.out.println(list);
    }

}

数据结构-基础线性表结构

C/C++/C#相关栏目本月热门文章