手写ArrayList、LinkedList

 ArrayList

package com.hjp.labs;

import org.omg.CORBA.PRIVATE_MEMBER;

/*
一、ArrayList的底层是Object类的数组，默认长度是10,超过10后，长度变为原长度的2倍+1。

二、可以简单的认为是一个动态数组；实际上ArrayList就是用数组实现的，长度不够时，调用Arrays.copyOf方法，拷贝当前数组到一个新的长度更大的数组。

三、特点：随机访问速度快，插入和移除性能较差(数组的特点)；

    支持null元素；

    有顺序；

    元素可以重复；

    线程不安全。
    参考：http://blog.csdn.net/smile_juan/article/details/7272841

*/
public class MyArrayList<T> {

    private static final int DEFAULT_CAPACITY = 10;
    private int size;
    private T[] items;

    public int size() {
        return size;
    }

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

    public void ensureCapacity(int newCapacity) {

        if (newCapacity < size()) {
            return;
        }

        T[] oldItems = items;
        items = (T[]) new Object[newCapacity];

        for (int i = 0; i < size(); i++) {
            items[i] = oldItems[i];
        }
    }

    public MyArrayList() {
        clear();
    }

    public void clear() {
        size = 0;
        ensureCapacity(DEFAULT_CAPACITY);
    }

    public T get(int index) {
        if (index <0 || index >= size())
            return null;

        return items[index];
    }

    public T set(int index, T newVal) {
        if (index < 0 || index >= size()) {
            return null;
        } else {
            T old = items[index];
            items[index] = newVal;
            return old;
        }
    }

    public boolean add(T x) {
        add(size(), x);
        return true;
    }

    public void add(int index, T x) {

        if (items.length == size())
            ensureCapacity(size() * 2 + 1);

        for (int i = size; i > index; i--) {
            items[i] = items[i - 1];
        }

        items[index] = x;
        size++;
    }

    public void remove(int index) {

        //T removeItem=items[index];
        for (int i = index; i < size() - 1; i++) {
            items[i] = items[i + 1];
        }

        size--;
    }

    public static void main(String[] args) {
        MyArrayList<String> list = new MyArrayList<String>();
        list.add("java");
        list.add("c++");
        list.add("c#");
        list.add(2,"php");

        for (int i = 0; i < list.size(); i++)
            System.out.println(list.get(i));
    }
}

LinkedList

package com.hjp.labs;

public class MyLinkedList<T> {

    /**
     * 结点类
     */
    private static class Node<T> {
        T nodeValue; // 数据域
        Node<T> next; // 指针域保存着下一节点的引用

        Node(T nodeValue, Node<T> next) {
            this.nodeValue = nodeValue;
            this.next = next;
        }

        Node(T nodeValue) {
            this(nodeValue, null);
        }
    }

    // 下面是SingleLinkedList类的数据成员和方法
    private Node<T> head, tail;

    public MyLinkedList() {
        head = tail = null;
    }

    /**
     * 判断链表是否为空
     */
    public boolean isEmpty() {
        return head == null;
    }

    /**
     * 创建头指针，该方法只用一次！
     */
    public void addToHead(T item) {
        head = new Node<T>(item);
        if(tail == null) tail = head;
    }

    /**
     * 添加尾指针，该方法使用多次
     */
    public void addToTail(T item) {
        if (!isEmpty()) { // 若链表非空那么将尾指针的next初使化为一个新的元素
            tail.next = new Node<T>(item); // 然后将尾指针指向现在它自己的下一个元素
            tail = tail.next;
        } else { // 如果为空则创建一个新的！并将头尾同时指向它
            head = tail = new Node<T>(item);
        }
    }

    /**
     * 打印列表
     */
    public void printList() {
        if (isEmpty()) {
            System.out.println("null");
        } else {
            for(Node<T> p = head; p != null; p = p.next)
                System.out.println(p.nodeValue);
        }
    }

    /**
     * 在表头插入结点，效率非常高
     */
    public void addFirst(T item) {
        Node<T> newNode = new Node<T>(item);
        newNode.next = head;
        head = newNode;
    }

    /**
     * 在表尾插入结点，效率很低
     */
    public void addLast(T item) {
        Node<T> newNode = new Node<T>(item);
        Node<T> p = head;
        while (p.next != null) p = p.next;
        p.next = newNode;
        newNode.next = null;
    }

    /**
     * 在表头删除结点，效率非常高
     */
    public void removeFirst() {
        if (!isEmpty()) head = head.next;
        else System.out.println("The list have been emptied!");
    }

    /**
     * 在表尾删除结点，效率很低
     */
    public void removeLast() {
        Node<T> prev = null, curr = head;
        while(curr.next != null) {
            prev = curr;
            curr = curr.next;
            if(curr.next == null) prev.next = null;
        }
    }

    /**
     * <p>插入一个新结点</p>
     * <ul>插入操作可能有四种情况:
     * <li>①表为空, 返回false</li>
     * <li>②表非空,指定的数据不存在</li>
     * <li>③指定的数据是表的第一个元素</li>
     * <li>④指定的数据在表的中间</li></ul>
     * @param appointedItem 指定的nodeValue
     * @param item 要插入的结点
     * @return 成功插入返回true;
     */
    public boolean insert(T appointedItem, T item) {
        Node<T>  prev = head, curr = head.next, newNode;
        newNode = new Node<T>(item);
        if(!isEmpty()) {
            while((curr != null) && (!appointedItem.equals(curr.nodeValue))) { //两个判断条件不能换
                prev = curr;
                curr = curr.next;
            }
            newNode.next = curr; //②③④
            prev.next = newNode;
            return true;
        }
        return false; //①
    }

    /**
     * <p>移除此列表中首次出现的指定元素</p>
     * <ul>删除操作可能出现的情况:
     * <li>①prev为空，这意味着curr为head. head = curr.next; --> removeFirst();</li>
     * <li>②匹配出现在列表中的某个中间位置，此时执行的操作是 --> prev.next = curr.next;,</li></ul>
     * <p>在列表中定位某个结点需要两个引用:一个对前一结点(prev左)的引用以及一个对当前结点(curr右)的引用.</p>
     * prev = curr;
     * curr = curr.next;
     */
    public void remove(T item) {
        Node<T> curr = head, prev = null;
        boolean found = false;
        while (curr != null && !found) {
            if (item.equals(curr.nodeValue)) {
                if(prev == null) removeFirst();
                else prev.next = curr.next;
                found = true;
            } else {
                prev = curr;
                curr = curr.next;
            }
        }
    }

    /**
     * 返回此列表中首次出现的指定元素的索引，如果列表中不包含此元素，则返回 -1.
     */
    public int indexOf(T item) {
        int index = 0;
        Node<T> p;
        for(p = head; p != null; p = p.next) {
            if(item.equals(p.nodeValue))
                return index;
            index++;

        }
        return -1;
    }

    /**
     * 如果此列表包含指定元素，则返回 true。
     */
    public boolean contains(T item) {
        return indexOf(item) != -1;
    }

    public static void main(String[] args) {
        MyLinkedList<String> t = new MyLinkedList<String>();
        t.addToHead("A");
        //t.addFirst("addFirst");
        t.addToTail("B");
        t.addToTail("C");
        System.out.println(t.indexOf("C")); // 2
        System.out.println(t.contains("A")); // true
        //t.addLast("addLast");
        //t.removeLast();
        //t.insert("B", "insert");
        //t.removeFirst();
        //t.remove("B"); // A C
        t.printList(); // A B C

    }
}