手写linkedlist 单向列表

/**
 * 单向链表实现
 * @param T
 */
public class LinkedListT {

    // 头节点
    private Node first;
    // 链表长度
    private int size;

    private LinkedList() {

        this.size = 0;
    }

    // 添加元素
    // 头插法
    private void put(T data) {

        Node head = first;
        Node curNode = new Node(data, head);
        first = curNode;
        size++;
    }

    // 指定位置添加元素
    private void put(int index, T data) {

        checkPositionIndex(index);
        Node pre = first;
        Node cur = first;
        for (int i = 0; i  index; i++) {

            pre = cur;
            cur = cur.next;
        }
        Node newNode = new Node(data, cur);
        pre.next = newNode;
        size++;
    }

    // 删除指定位置元素
    public T remove(int index) {

        checkPositionIndex(index);
        Node pre = first;
        Node cur = first;
        for (int i = 0; i  index; i++) {

            pre = cur;
            cur = cur.next;
        }
        pre.next = cur.next;
        cur.next = null; // GC
        size--;
        return cur.data;
    }

    // 删除最后一个元素
    public T removeLast() {

        return this.remove(size-1);
    }

    // 修改指定位置元素
    private void set(int index, T data) {

        checkPositionIndex(index);
        Node cur = first;
        for (int i = 0; i  index; i++) {

            cur = cur.next;
        }
        cur.data = data;
    }

    // 查看指定位置元素
    private T get(int index) {

        checkPositionIndex(index);
        Node cur = first;
        for (int i = 0; i  index; i++) {

            cur = cur.next;
        }
        return cur.data;
    }

    // 返回链表长度
    private int size() {

        return size;
    }

    @Override
    public String toString() {

        Node cur = first;
        for (int i = 0; i  size; i++) {

            System.out.print(cur.data + "  ");
            cur = cur.next;
        }
        System.out.println();
        return super.toString();
    }

    // 检查索引
    private void checkPositionIndex(int index) {

        if (!(index = 0  index = size)) {

            throw new IllegalArgumentException("index: " + index + ", size: " + size);
        }
    }

    private class Node {

        private T data;
        private Node next;

        Node(T data, Node next) {
            this.data = data;
            this.next = next;
        }
    }

    public static void main(String[] args) {

        LinkedListInteger list = new LinkedList();

        for (int i = 0; i  5; i++) {

            list.put(i);
        }

        list.toString();
        list.set(3,2);
        list.toString();
        list.put(18);
        list.toString();
        list.put(2, 20);
        list.toString();
        System.out.println(list.get(2));
        System.out.println(list.size());
        list.remove(1);
        list.toString();
        list.removeLast();
        list.toString();
        list.removeLast();
        list.toString();
    }
}

输出结果:

4  3  2  1  0  
4  3  2  2  0  
18  4  3  2  2  0  
18  4  20  3  2  2  0  
20
7
18  20  3  2  2  0  
18  20  3  2  2  
18  20  3  2  

Process finished with exit code 0

最新回复(0)
/jishuoSwm1O00tqEUXPQdehHpx6TqxMErv_2FLWgvMk7g_3D_3D4489002
8