数据结构线性表以及Java代码实现

灰太狼 2022-06-12 04:07 205阅读 0赞

## 1. 线性表 ##

**线性表**是最基本、最简单、也是最常用的一种数据结构。在线性表中数据元素之间的关系是线性，数据元素可以看成是排列在一条线上或一个环上。  
线性表分为**静态线性表**和**动态线性表**，常见的有**顺序表**(**静态的**)、**单向链表**(**动态的**)和**双向链表**(**动态的**)。

## 2. 顺序表 ##

![这里写图片描述][1358230065_6547.png]

/** * List * 线性表接口 * （1）计算表的长度n。 * （2）线性表是否为空 * （3）将元素添加到线性表的末尾 * （4）获取第i个元素，0≤i < n。 * （5）清除线性表 * （6）返回列表中首次出现指定元素的索引，如果列表不包含此元素，则返回 -1。 * （7）返回列表中最后一次出现指定元素的索引，如果列表不包含此元素，则返回 -1。 * （8）将新元素插入第i个位置，0≤i < n，使原来的第i，i+1，…，n–1个元素变为第i+1，i+2，…，n个元素。 * （9）更改第i个元素 * （10）删除第i个元素，0≤i < n，使原来的第i+1，i+2，…，n–1个元素变为第i，i+1，…，n–2个元素 * Created by heqianqian on 2017/7/13. */
    public interface List<T> {
    
        /** * 计算表的长度 */
        int getLength();
    
        /** * 判断表是否为空 */
        boolean isEmpty();
    
        /** * 将元素添加到线性表的末尾 */
        boolean add(T entity);
    
        /** * 获取第index个元素 */
        T get(int index);
    
        /** * 清除线性表 */
        void clear();
    
        /** * 返回列表中首次出现指定元素的索引，如果列表不包含此元素，则返回 -1。 */
        int indexOf(T entity);
    
        /** * 返回列表中最后一次出现指定元素的索引，如果列表不包含此元素，则返回 -1。 */
        int lastIndexOf(T entity);
    
        /** * 将新元素插入第index个位置，0≤index< n */
        boolean insert(T entity,int index);
    
        /** * 更改第index个元素 */
        boolean update(T entity,int index);
    
        /** * 删除第index个元素 */
        boolean delete(int index);
    
    }

/** * ArrayList * 线性表的实现 * Created by heqianqian on 2017/7/13. */
    public class ArrayList<T> implements List<T> {
    
        private T[] t;
        private int size = 0;//当前可以插入元素的位置
        private int maxLen;
        private static final int LIST_LENGTH = 10;
    
        @SuppressWarnings("unchecked")
        public ArrayList() {
            maxLen = LIST_LENGTH;
            t = (T[]) new Object[maxLen];
        }
    
        @SuppressWarnings("unchecked")
        public ArrayList(int length) {
            maxLen = length;
            t = (T[]) new Object[maxLen];
        }
    
        @Override
        public int getLength() {
            return size;
        }
    
        @Override
        public boolean isEmpty() {
            return size == 0;
        }
    
        @Override
        public boolean add(T entity) {
            if (size == maxLen) {
       //数组已满
                expand();//扩充数组大小
            }
            //添加元素 元素个数+1
            t[size++] = entity;
            return true;
        }
    
        @Override
        public T get(int index) {
           calIndex(index);
            return t[index];
        }
    
        @Override
        public void clear() {
            size = 0;
        }
    
        @Override
        public int indexOf(T entity) {
            for (int i = 0; i < size; i++) {
                if (t[i].equals(entity)) {
                    return i;
                }
            }
            return -1;
        }
    
        @Override
        public int lastIndexOf(T entity) {
            for (int i = size - 1; i >= 0; i--) {
                if (t[i].equals(entity)) {
                    return i;
                }
            }
            return -1;
        }
    
        @Override
        public boolean insert(T entity, int index) {
            calIndex(index);
            if (size > maxLen) {
                expand();//扩充数组大小
            }
            //index-size-1元素后移一位
            for (int i = size; i > index; i--) {
                t[i] = t[i - 1];
            }
            t[index] = entity;
            size++;
            return true;
        }
    
        @Override
        public boolean update(T entity, int index) {
            return insert(entity, index);//TODO
        }
    
        @Override
        public boolean delete(int index) {
            calIndex(index);
            for (int i = index; i < size - 2; i++) {
                t[i] = t[i + 1];
                System.out.println(this);
            }
            size--;
            return true;
        }
    
        /** * 扩充数组大小 * 按照原大小扩大一倍 */
        @SuppressWarnings("unchecked")
        private void expand() {
            T[] t1 = (T[]) new Object[maxLen * 2];
            System.arraycopy(t, 0, t1, 0, size);
            t = t1;
        }
    
        /** * 判断数组下标是否正确 */
        private void calIndex(int index) {
            if (index < 0) {
                throw new IllegalArgumentException("非法数组下标");
            }
            if (index > size) {
                throw new ArrayIndexOutOfBoundsException("数组下标越界");
            }
        }
    
        @Override
        public String toString() {
            StringBuilder sb = new StringBuilder();
            sb.append("[");
            for (int i = 0; i < size - 1; i++) {
                sb.append(t[i]).append(",");
            }
            sb.append(t[size - 1]).append("]");
            return sb.toString();
        }
    }

## 2.单向循环链表 ##

![这里写图片描述][1358230199_7401.png]

/** * 单向循环列表 * Created by heqianqian on 2017/7/13. */
    public class Node<T> { 
    
        /** * 尾指针 */
        public Node next;
    
        /** * 数据域 */
        public T data;
    
        @SuppressWarnings("unchecked")
        public Node() {
            data = (T) new Object();
            next = null;
        }
    
        public Node(T data) {
            this.data = data;
            next = null;
        }
    
        @Override
        public String toString() {
            return data.toString();
        }
    }

/** * LinkedList * 单向循环列表 * Created by heqianqian on 2017/7/13. */
    public class LinkedList<T> implements List<T> { 
    
        /** * 头指针 */
        private Node<T> head;
    
        /** * 指向链表尾部 便于遍历 */
        private Node<T> current;
    
        /** * 当前链表的大小 */
        private int size = 0;
    
        @SuppressWarnings("unchecked")
        public LinkedList() {
            head = new Node<T>();
            current = new Node<T>();
            //当前指向头指针
            head = current;
        }
    
        @Override
        public int getLength() {
            return size;
        }
    
        @Override
        public boolean isEmpty() {
            return head.next == null;
        }
    
        @Override
        @SuppressWarnings("unchecked")
        public boolean add(T entity) {
            //要插入的节点
            Node<T> node = new Node<T>(entity);
            current.next = node;
            current = node;
            size++;
            return true;
        }
    
        @Override
        @SuppressWarnings("unchecked")
        public T get(int index) {
            calIndex(index);
            return (T) getNode(index).data;
        }
    
        @Override
        public void clear() {
            size = 0;
            current = head;
            head.next = null;
        }
    
        @Override
        public int indexOf(T entity) {
            Node node = head;
            int index = -1;
            while (node.next != null && !node.data.equals(entity)) {
                node = node.next;
                index++;
            }
            if (index == size - 1) {
                return -1;
            }
            return index;
        }
    
    
    
        @Override
        public int lastIndexOf(T entity) {
            return 0;
        }
    
        @Override
        @SuppressWarnings("unchecked")
        public boolean insert(T entity, int index) {
            calIndex(index);
            Node node = getNode(index);
            Node newNode = new Node(entity);
            newNode.next = node.next;
            node.next = newNode;//current指针 不变
            size++;
            return true;
        }
    
        @Override
        public boolean update(T entity, int index) {
            return insert(entity, index);
        }
    
        @Override
        public boolean delete(int index) {
            calIndex(index);
            Node node = head.next;
            for (int i = 0; i < index; i++) {
                node = node.next;
            }
            node.next = node.next.next;
            return false;
        }
    
        /** * 判断数组下标是否正确 */
        private void calIndex(int index) {
            if (index < 0) {
                throw new IllegalArgumentException("非法数组下标");
            }
            if (index > size) {
                throw new ArrayIndexOutOfBoundsException("数组下标越界");
            }
        }
    
        /** * 获取第index个节点 */
        private Node getNode(int index) {
            Node n = head;
            for (int i = 0; i < index; i++) {
                n = n.next;
            }
            return n;
        }
    
        @Override
        public String toString() {
            StringBuilder sb = new StringBuilder();
            sb.append("[");
            Node node = head.next;
            while (node != null) {
                sb.append(node.toString()).append(",");
                node = node.next;
            }
            sb.append("]");
            return sb.toString();
        }
    }

## 3.双向循环链表 ##

![这里写图片描述][1358230351_7951.png]

/** * DLNode * Created by heqianqian on 2017/7/14. */
    public class DLNode<T> {
    
        public T data;
    
        public DLNode<T> prio;
    
        public DLNode<T> next;
    
        public DLNode() {
        }
    
        public DLNode(T data) {
            this.data = data;
            prio = null;
            next = null;
        }
    
        @Override
        public String toString() {
            return data.toString();
        }
    }

/** * DoubleLinkedList * Created by heqianqian on 2017/7/14. */
    public class DoubleLinkedList<T> implements List<T> { 
    
        private DLNode<T> head;
        private DLNode<T> current;
        private int size;
    
        public DoubleLinkedList() {
            head = new DLNode<T>();
            head.next = head;
            head.prio = head;
            current = head;
            size = 0;
        }
    
        @Override
        public int getLength() {
            return size;
        }
    
        @Override
        public boolean isEmpty() {
            return size == 0;
        }
    
        @Override
        public boolean add(T entity) {
            DLNode<T> node = new DLNode<T>(entity);
            node.next = current.next;
            node.prio = current;
            current.next = node;
            current = node;
            size++;
            return true;
        }
    
        @Override
        public T get(int index) {
            calIndex(index);
            return getIndex(index).data;
        }
    
        @Override
        public void clear() {
            size = 0;
            head.next = head;
            head.prio = head;
            current = head;
        }
    
        @Override
        public int indexOf(T entity) {
            DLNode<T> temp = head.next;
            int index = 0;
            while (temp.next != head && !temp.data.equals(entity)) {
                temp = temp.next;
                index++;
            }
            if (index >= size - 1) {
                return -1;
            }
            return index;
        }
    
        @Override
        public int lastIndexOf(T entity) {
            DLNode<T> node = head.prio;
            int index = size;
            while (node.prio != head && !node.data.equals(entity)) {
                node = node.prio;
                index--;
            }
            if (index >= size - 1) {
                return -1;
            }
            return index;
        }
    
        @Override
        public boolean insert(T entity, int index) {
            calIndex(index);
            DLNode<T> node = new DLNode<T>(entity);
            DLNode<T> temp = getIndex(index - 1);
            node.next = temp.next;
            node.prio = temp;
            temp.next = node;
            size++;
            return true;
        }
    
        @Override
        public boolean update(T entity, int index) {
            return insert(entity, index);
        }
    
        @Override
        public boolean delete(int index) {
            calIndex(index);
            DLNode<T> temp = getIndex(index - 1);
            temp.next.next.prio = temp;
            temp.next = temp.next.next;
            size--;
            return true;
        }
    
        /** * 判断数组下标是否正确 */
        private void calIndex(int index) {
            if (index < 0) {
                throw new IllegalArgumentException("非法数组下标");
            }
            if (index > size) {
                throw new ArrayIndexOutOfBoundsException("数组下标越界");
            }
        }
    
        /** * 获得第index个节点 */
        private DLNode<T> getIndex(int index) {
            DLNode<T> temp = head.next;
            for (int i = 0; i < index; i++) {
                temp = temp.next;
            }
            return temp;
        }
    
        @Override
        public String toString() {
            StringBuilder sb = new StringBuilder();
            sb.append("[");
            DLNode<T> temp = head.next;
            for (int i = 0; i < size - 1; i++) {
                sb.append(temp.data.toString()).append(",");
                temp = temp.next;
            }
            sb.append(temp.data.toString());
            sb.append("]");
            return sb.toString();
        }
    }

[1358230065_6547.png]: https://img-my.csdn.net/uploads/201301/15/1358230065_6547.png
[1358230199_7401.png]: https://img-my.csdn.net/uploads/201301/15/1358230199_7401.png
[1358230351_7951.png]: https://img-my.csdn.net/uploads/201301/15/1358230351_7951.png