Java 线性表，

#先实现线性表的 Interface

public interface List<E> {
    boolean isEmpty();
    int length();
    Object get(int index);
    // 设置第index个元素的值为elem
    void set(int index, E elem);    
    // 返回elem在表中的位置
    int locate(E elem);
    // 表尾添加elem
    void add(E elem);
    // 在index处添加elem
    void add(int index, E elem);
    // 删除表尾元素
    E remove();
    // 删除第index个元素
    E remove(int index);
    // 遍历表
    void traverse();
}

Java顺序表实现代码

import java.util.Arrays;

public class SequenceList<E> implements List<E> {
    private final int ADD_SIZE = 10;
    private int capacity = 10;
    private int size = 0;
    private Object[] data;

    public Object[] getData() {
        return data;
    }

    public SequenceList() {
        data = new Object[this.capacity];
    }

    public SequenceList(int length) {
        capacity = length;
        data = new Object[capacity];
    }

    private void addCapacity() {
        capacity += ADD_SIZE;
        data = Arrays.copyOf(data, capacity);
    }

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

    public int length() {
        return size;
    }

    public void clear() {
        Arrays.fill(data, null);
        size = 0;
    }

    public E get(int index) {
        if (index < 1 || index > size) {
            System.out.println("invalid index");
            return null;
        }
        return (E) data[index - 1];
    }

    @Override
    public void set(int index, E elem) {
        if (index < 1 || index > size) return;
        data[index - 1] = elem;
    }

    public int locate(E elem) {
        for (int i = 0; i < size; i++) {
            if (data[i].equals(elem))
                return i + 1;
        }
        return 0;
    }

    public void add(E elem) {
        add(size + 1, elem);
    }

    public void add(int index, E elem) {
        if (index < 1 || index > size + 1) {
            System.out.println("invalid index");
            return;
        }
        if (size == capacity) {
            addCapacity();
        }
        for (int i = size; i > index - 1; i--)
            data[i] = data[i - 1];
        data[index - 1] = elem;
        size++;
    }

    public E remove() {
        return remove(size);
    }

    public E remove(int index) {
        if (index < 1 || index > size) {
            System.out.println("Invalid index");
            return null;
        }
        E elem = (E) data[index - 1];
        for (int i = index; i < size; i++)
            data[i - 1] = data[i];
        size--;
        return elem;
    }

    // 得到this和r的并集
    public void union(SequenceList<E> r) {
        int lenR = r.length();
        for (int i = 0; i < lenR; i++) {
            E dataR = (E) r.getData()[i];
            if (locate(dataR) == 0)
                add(size + 1, dataR);
        }
    }

    public void traverse() {
        for (int i = 0; i < size; i++)
            System.out.print(data[i] + "\t");
        System.out.println();
    }

    public static void main(String[] args) {
        SequenceList<Integer> list1 = new SequenceList<>();
        SequenceList<Integer> list2 = new SequenceList<>();
        for (int i = 0; i < 6; i++) {
            list1.add(i * 2);
            list2.add(i * 2 + 1);
        }
        list1.add(1, -1);
        list2.add(-2);
        list2.remove(1);
        list1.remove();
        list1.traverse();
        list2.traverse();
        list1.union(list2);
        list1.traverse();
    }
}

#Java链式单向表实现代码

public class LinkList<E> implements List<E> {
    class Node<E> {
        private E data;
        private Node<E> next;

        public Node() {
            this(null);
        }

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

        public E getData() {
            return data;
        }
    }

    //head不存储元素, 指向首元素
    private Node<E> head;
    private int size = 0;

    public LinkList() {
        head = new Node<>();
    }

    public boolean isEmpty() {
        return head.next == null;
    }

    public int length() {
        return size;
    }

    private Node<E> getData(int index) {
        if (index < 1 || index > size) {
            System.out.println("Invalid index");
            return null;
        }
        Node<E> tmp = head.next;
        while (index > 1) {
            tmp = tmp.next;
            index--;
        }
        return tmp;
    }

    public E get(int index) {
        return getData(index).getData();
    }

    public void set(int index, E elem) {
        Node<E> tmp = getData(index);
        tmp.data = elem;
    }

    public int locate(E elem) {
        Node<E> tmp = head.next;
        for (int index = 0; tmp != null; index++, tmp = tmp.next) {
            if (tmp.getData().equals(elem))
                return index + 1;
        }
        return 0;
    }

    public void add(E elem) {
        add(size + 1, elem);
    }

    public void add(int index, E elem) {
        Node<E> tmp;
        if (index == 1)
            tmp = head;
        else if ((tmp = getData(index - 1)) == null)
            return;
        Node<E> newNode = new Node<>(elem);
        newNode.next = tmp.next;
        tmp.next = newNode;
        size++;
    }

    public E remove() {
        return remove(size);
    }

    public E remove(int index) {
        Node<E> tmp;
        if (index == 1)
            tmp = head;
        else if ((tmp = getData(index - 1)) == null)
            return null;
        Node<E> target = tmp.next;
        tmp.next = target.next;
        E elem = target.getData();
        target.data = null;
        size--;
        return elem;
    }

    public void traverse() {
        Node<E> tmp = head.next;
        for (int i = 0; i < size; i++, tmp = tmp.next)
            System.out.print(tmp.getData() + "\t");
        System.out.println();
    }

    public static void main(String[] args) {
        LinkList<Integer> list1 = new LinkList<>();
        list1.add(1);
        list1.add(2);
        list1.add(3);
        list1.add(4);
        list1.add(5);
        list1.add(2, 6);
        list1.remove();
        list1.remove(1);
        list1.traverse();
    }

}

#Java双向链表实现代码

public class DoubleLinkList<E> implements List<E> {
    private class Node<E> {
        E data;
        Node<E> prev;
        Node<E> next;

        public Node() {
            this(null);
        }

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

        public E getData() {
            return data;
        }
    }

    // first 不存储元素 指向首元素 last是尾元素
    private Node<E> first;
    private Node<E> last;
    private int size = 0;

    public DoubleLinkList() {
        first = new Node<>();
        last = new Node<>();
        first = last;
    }

    public boolean isEmpty() {
        return last == null;
    }

    public int length() {
        return size;
    }

    public void clear() {
        Node<E> tmp = last.prev;
        while (size > 0) {
            tmp.next = null;
            size--;
        }
    }

    public Node<E> getData(int index) {
        if (index < 1 || index > size) {
            System.out.println("Invalid index");
            return null;
        }
        if (2 * index < size) {
            return getFromFirst(index);
        } else {
            return getFromLast(index);
        }
    }

    public E get(int index) {
        return getData(index).getData();
    }

    @Override
    public void set(int index, E elem) {
        Node<E> tmp = getData(index);
        tmp.data = elem;
    }

    private Node<E> getFromFirst(int index) {
        Node<E> tmp = first.next;
        while (index > 1) {
            tmp = tmp.next;
            index--;
        }
        return tmp;
    }

    private Node<E> getFromLast(int index) {
        Node<E> tmp = last;
        while (index < size) {
            tmp = tmp.prev;
            index++;
        }
        return tmp;
    }

    public int locate(E elem) {
        Node<E> tmp = first;
        for (int i = 0; i < size; i++) {
            tmp = tmp.next;
            if (tmp.getData().equals(elem))
                return i + 1;
        }
        return 0;
    }

    public void add(E elem) {
        Node<E> newNode = new Node<>(elem);
        last.next = newNode;
        newNode.prev = last;
        last = newNode;
        size++;
    }

    public void add(int index, E elem) {
        if (index == size + 1)
            add(elem);
        Node<E> tmp = getData(index);
        Node<E> newNode = new Node<>(elem);
        tmp.prev.next = newNode;
        newNode.prev = tmp.next;
        newNode.next = tmp;
        tmp.prev = newNode;
        size++;
    }

    public E remove() {
        E elem = last.getData();
        last.data = null;
        last = last.prev;
        last.next = null;
        size--;
        return elem;
    }

    public E remove(int index) {
        if (index == size)
            return remove();
        Node<E> tmp = getData(index);
        tmp.prev.next = tmp.next;
        tmp.next.prev = tmp.prev;
        E elem = tmp.data;
        tmp.data = null;
        size--;
        return elem;
    }

    public void traverse() {
        Node<E> tmp = first.next;
        for (int i = 0; i < size; i++, tmp = tmp.next)
            System.out.print(tmp.getData() + "\t");
        System.out.println();
    }

    public static void main(String[] args) {
        DoubleLinkList<Integer> list = new DoubleLinkList<>();
        list.add(1);
        list.add(2);
        list.add(3);
        list.add(2, 4);
        list.add(5);
        list.remove(1);
        list.remove();
        list.add(6);
        list.remove(3);
        list.traverse();
    }

}