Java实现链表

一、什么是链表

链表是一种常用的线性数据结构，它由一系列结点（Node）组成。每个结点包含数据域和指针域，其中数据域存储结点的数据信息，指针域存储下一个结点的地址。链表中的结点可以在任何时间动态添加或删除。

二、链表的分类

链表可以分为单向链表、双向链表和循环链表三种类型。

• 单向链表: 每个结点只有一个指针域，指向下一结点。
• 双向链表: 每个结点有两个指针域，分别指向前驱结点和后继结点。
• 循环链表: 单向循环链表和双向循环链表是两种形式的循环链表，它们的规则都是把链表的头结点和尾结点相连从而形成一个环。

三、Java实现单向链表

下面的代码展示了如何使用Java实现单向链表:

class Node {  
    // 数据域  
    private int data;  
    // 指针域  
    private Node next;  
  
    public Node(int data, Node next) {  
        this.data = data;  
        this.next = next;  
    }  
  
    public int getData() {  
        return data;  
    }  
  
    public void setData(int data) {  
        this.data = data;  
    }  
  
    public Node getNext() {  
        return next;  
    }  
  
    public void setNext(Node next) {  
        this.next = next;  
    }  
}  
  
class LinkedList {  
    // 头结点  
    private Node head;  
    // 链表长度  
    private int size;  
  
    public LinkedList() {  
        // 初始化头结点，next指向null  
        head = new Node(0, null);  
        size = 0;  
    }  
  
    // 根据index获取结点  
    private Node getNode(int index) {  
        if (index < 0 || index >= size) {  
            throw new IndexOutOfBoundsException();  
        }  
        Node node = head.getNext();  
        for (int i = 0; i < index; i++) {  
            node = node.getNext();  
        }  
        return node;  
    }  
  
    // 插入结点  
    public void add(int index, int data) {  
        if (index < 0 || index > size) {  
            throw new IndexOutOfBoundsException();  
        }  
        Node prev = head;  
        for (int i = 0; i < index; i++) {  
            prev = prev.getNext();  
        }  
        Node node = new Node(data, prev.getNext());  
        prev.setNext(node);  
        size++;  
    }  
  
    // 删除结点  
    public void remove(int index) {  
        if (index < 0 || index >= size) {  
            throw new IndexOutOfBoundsException();  
        }  
        Node prev = head;  
        for (int i = 0; i < index; i++) {  
            prev = prev.getNext();  
        }  
        Node node = prev.getNext();  
        prev.setNext(node.getNext());  
        size--;  
    }  
  
    // 修改结点  
    public void set(int index, int data) {  
        if (index < 0 || index >= size) {  
            throw new IndexOutOfBoundsException();  
        }  
        Node node = getNode(index);  
        node.setData(data);  
    }  
  
    // 获取链表长度  
    public int getSize() {  
        return size;  
    }  
  
    // 获取结点数据  
    public int get(int index) {  
        if (index < 0 || index >= size) {  
            throw new IndexOutOfBoundsException();  
        }  
        Node node = getNode(index);  
        return node.getData();  
    }  
} 

上面的代码中，LinkedList类包含了add、remove、set、getSize和get方法，分别实现了插入结点、删除结点、修改结点、获取链表长度和获取结点数据的功能。同时，Node类表示链表的每个结点，包含数据域和指针域。

四、Java实现双向链表

双向链表由于结点有前驱结点和后继结点两个指针域，所以需要在Node类中添加前驱指针域prev。同时，在链表插入和删除操作时还需要处理前驱结点的后继指针。

下面的代码展示了如何使用Java实现双向链表:

class Node {  
    // 数据域  
    private int data;  
    // 前驱指针域  
    private Node prev;  
    // 后继指针域  
    private Node next;  
  
    public Node(int data, Node prev, Node next) {  
        this.data = data;  
        this.prev = prev;  
        this.next = next;  
    }  
  
    public int getData() {  
        return data;  
    }  
  
    public void setData(int data) {  
        this.data = data;  
    }  
  
    public Node getPrev() {  
        return prev;  
    }  
  
    public void setPrev(Node prev) {  
        this.prev = prev;  
    }  
  
    public Node getNext() {  
        return next;  
    }  
  
    public void setNext(Node next) {  
        this.next = next;  
    }  
}  
  
class DoublyLinkedList {  
    // 头结点  
    private Node head;  
    // 尾结点  
    private Node tail;  
    // 链表长度  
    private int size;  
  
    public DoublyLinkedList() {  
        // 初始化头结点和尾结点，prev和next分别指向null  
        head = new Node(0, null, null);  
        tail = new Node(0, head, null);  
        head.setNext(tail);  
        size = 0;  
    }  
  
    // 根据index获取结点  
    private Node getNode(int index) {  
        if (index < 0 || index >= size) {  
            throw new IndexOutOfBoundsException();  
        }  
        Node node;  
        if (index < size / 2) {  
            // 从前往后遍历  
            node = head.getNext();  
            for (int i = 0; i < index; i++) {  
                node = node.getNext();  
            }  
        } else {  
            // 从后往前遍历  
            node = tail;  
            for (int i = size; i > index; i--) {  
                node = node.getPrev();  
            }  
        }  
        return node;  
    }  
  
    // 插入结点  
    public void add(int index, int data) {  
        if (index < 0 || index > size) {  
            throw new IndexOutOfBoundsException();  
        }  
        Node next = getNode(index);  
        Node prev = next.getPrev();  
        Node node = new Node(data, prev, next);  
        prev.setNext(node);  
        next.setPrev(node);  
        size++;  
    }  
  
    // 删除结点  
    public void remove(int index) {  
        if (index < 0 || index >= size) {  
            throw new IndexOutOfBoundsException();  
        }  
        Node node = getNode(index);  
        Node prev = node.getPrev();  
        Node next = node.getNext();  
        prev.setNext(next);  
        next.setPrev(prev);  
        size--;  
    }  
  
    // 修改结点  
    public void set(int index, int data) {  
        if (index < 0 || index >= size) {  
            throw new IndexOutOfBoundsException();  
        }  
        Node node = getNode(index);  
        node.setData(data);  
    }  
  
    // 获取链表长度  
    public int getSize() {  
        return size;  
    }  
  
    // 获取结点数据  
    public int get(int index) {  
        if (index < 0 || index >= size) {  
            throw new IndexOutOfBoundsException();  
        }  
        Node node = getNode(index);  
        return node.getData();  
    }  
} 

上面的代码中，DoublyLinkedList类包含了add、remove、set、getSize和get方法，和LinkedList类相比需要多处理前驱指针和后继指针的更新。同时，Node类表示链表的每个结点，包含数据域、前驱指针域和后继指针域。

五、Java实现循环链表

循环链表在单向链表和双向链表的基础上，把链表的头结点和尾结点相连从而形成一个环。在插入和删除结点时，如果操作的位置是头结点或尾结点则需要更新尾结点和头结点的指针。

下面的代码展示了如何使用Java实现单向循环链表:

class Node {  
    // 数据域  
    private int data;  
    // 指针域  
    private Node next;  
  
    public Node(int data, Node next) {  
        this.data = data;  
        this.next = next;  
    }  
  
    public int getData() {  
        return data;  
    }  
  
    public void setData(int data) {  
        this.data = data;  
    }  
  
    public Node getNext() {  
        return next;  
    }  
  
    public void setNext(Node next) {  
        this.next = next;  
    }  
}  
  
class CircularLinkedList {  
    // 头结点  
    private Node head;  
    // 链表长度  
    private int size;  
  
    public CircularLinkedList() {  
        // 初始化头结点，next指向自身  
        head = new Node(0, null);  
        head.setNext(head);  
        size = 0;  
    }  
  
    // 根据index获取结点  
    private Node getNode(int index) {  
        if (index < 0 || index >= size) {  
            throw new IndexOutOfBoundsException();  
        }  
        Node node = head.getNext();  
        for (int i = 0; i < index; i++) {  
            node = node.getNext();  
        }  
        return node;  
    }  
  
    // 插入结点  
    public void add(int index, int data) {  
        if (index < 0 || index > size) {  
            throw new IndexOutOfBoundsException();  
        }  
        if (index == size) {  
            // 插入尾结点  
            Node tail = head;  
            for (int i = 0; i < size; i++) {  
                tail = tail.getNext();  
            }  
            Node node = new Node(data, head);  
            tail.setNext(node);  
        } else {  
            Node prev = head;  
            for (int i = 0; i < index; i++) {  
                prev = prev.getNext();  
            }  
            Node node = new Node(data, prev.getNext());  
            prev.setNext(node);  
        }  
        size++;  
    }  
  
    // 删除结点  
    public void remove(int index) {  
        if (index < 0 || index >= size) {  
            throw new IndexOutOfBoundsException();  
        }  
        if (index == size - 1) {  
            // 删除尾结点  
            Node tail = head;  
            for (int i = 0; i < size; i++) {  
                tail = tail.getNext();  
            }  
            Node prev = getNode(index - 1);  
            prev.setNext(head);  
            tail = prev;  
        } else {  
            Node prev = head;  
            for (int i = 0; i < index; i++) {  
                prev = prev.getNext();  
            }  
            Node node = prev.getNext();  
            prev.setNext(node.getNext());  
        }  
        size--;  
    }  
  
    // 修改结点  
    public void set(int index, int data) {  
        if (index < 0 || index >= size) {  
            throw new IndexOutOfBoundsException();  
        }  
        Node node = getNode(index);  
        node.setData(data);  
    }  
  
    // 获取链表长度  
    public int getSize() {  
        return size;  
    }  
  
    // 获取结点数据  
    public int get(int index) {  
        if (index < 0 || index >= size) {  
            throw new IndexOutOfBoundsException();  
        }  
        Node node = getNode(index);  
        return node.getData();  
    }  
} 

上面的代码中，CircularLinkedList类包含了add、remove、set、getSize和get方法，和LinkedList类相比需要多处理尾结点的指针。同时，Node类表示链表的每个结点，包含数据域和指针