单向链表模拟实现

模拟LinckedList实现增删改查

• ps:未考虑并发情况
• 链表结构优点，删除，插入数据速度快，占用内存小。

public class LinkedListDemo {

    public static void main(String[] args) {
        // TODO Auto-generated method stub
        LinkedList linkedList = new LinkedList();
        linkedList.add(new Node("aaaa"));
        linkedList.add(new Node("bbbb"));
        linkedList.add(new Node("cccc1"));
        linkedList.add(new Node("cccc2"));
        linkedList.add(new Node("cccc3"));
        linkedList.add(new Node("cccc4"));
        linkedList.add(new Node("cccc5"));

        // linkedList.insert(new Node("hahahaah"), 4);
        // linkedList.delete(new Node("cccc1"));
        // linkedList.delete(new Node("cccc3"));
        // linkedList.delete(new Node("cccc4"));
        // linkedList.delete(0);
        // linkedList.delete(6);
        // linkedList.update(new Node("cccc2"), "aaaaaaaaaaaaaaaaaaaaaaaaa");
        // linkedList.update(5, "aaaaaaaaaaaaaaaaaaaaaaaaa");
        // System.out.println(linkedList.getPosition(new Node("aaaa")));
        // System.out.println(linkedList.getPosition(new Node("cccc2")));
        // System.out.println(linkedList.getPosition(new Node("ccccss2")));

        // System.out.println(linkedList.contain(new Node("cccc1")));
        // linkedList.traverse();
    }

}

class LinkedList {
    Node head;
    Node tail;
    int length;

    public LinkedList() {
        // TODO Auto-generated constructor stub
    }

    public void add(Node node) {
        if (head == null) {
            head = node;
            tail = node;
            length++;
        } else {
            tail.setNext(node);
            tail = node;
            length++;
        }
    }

    public void insert(Node node, int pos) {

        if (pos > length) {
            throw new RuntimeException("超出角标");
        }
        if (pos == 0) {
            Node temp = head;
            head = node;
            node.setNext(temp);
            length++;
            return;
        }
        if (pos == length) {
            tail.setNext(node);
            tail = node;
            length++;
            return;
        }
        Node previous = head;
        for (int i = 1; i < length; i++) {
            if (pos == i) {
                Node temp = previous.next;
                previous.setNext(node);
                node.setNext(temp);
                length++;
                return;
            }
            previous = previous.next;
        }
    }

    public void delete(Node node) {
        if (node.equals(head)) {
            head = head.next;
            length--;
            return;
        }
        Node previous = head;
        for (int i = 1; i < length; i++) {
            if (previous.next.equals(node)) {
                Node temp = previous.next.next;
                previous.setNext(temp);
                length--;
                return;
            }
            previous = previous.next;
        }
        throw new RuntimeException("not found");
    }

    public void delete(int pos) {
        if (pos == 0) {
            head = head.next;
            length--;
            return;
        }
        Node previous = head;
        for (int i = 1; i < length; i++) {
            if (pos == i) {
                Node temp = previous.next.next;
                previous.setNext(temp);
                length--;
                return;
            }
            previous = previous.next;
        }
        throw new RuntimeException("not found");

    }

    public void update(Node node, String data) {
        Node current = head;
        for (int i = 0; i < length; i++) {
            if (current.equals(node)) {
                current.setData(data);
                return;
            }
            current = current.next;
        }

        throw new RuntimeException("not found");
    }

    public void update(int pos, String data) {
        Node current = head;
        for (int i = 0; i < length; i++) {
            if (pos == i) {
                current.setData(data);
                return;
            }
            current = current.next;
        }

        throw new RuntimeException("not found");
    }

    public int getPosition(Node node) {
        Node current = head;
        for (int i = 0; i < length; i++) {
            if (current.equals(node)) {
                return i;
            }
            current = current.next;
        }

        return -1;
    }

    public boolean contain(Node node) {
        return !(getPosition(node) == -1);
    }

    public void traverse() {
        Node current = head;
        for (int i = 0; i < length; i++) {
            System.out.println(current.data);
            current = current.next;
        }
    }

    public int size() {
        return length;
    }

}

class Node {
    String data;
    Node next;

    Node(String data) {
        this.data = data;
    }

    public String getData() {
        return data;
    }

    public void setData(String data) {
        this.data = data;
    }

    public Node getNext() {
        return next;
    }

    public void setNext(Node next) {
        this.next = next;
    }

    public boolean equals(Object obj) {
        if (!(obj instanceof Node)) {
            throw new RuntimeException("cast exception");
        }
        Node compare = (Node) obj;
        return this.data.equals(compare.data);
    }

}