Java链表实现

链表（Linked List）是一种常见的数据结构，它由一系列节点组成，其中每个节点包含数据和指向下一个节点的引用。相对于数组，链表在插入和删除操作时具有更好的优势，因为数组需要在内存中移动元素，而链表只需要更改链接。

一、Java链表实现简介

Java提供了实现链表结构的数据结构，其中主要包括LinkedList和List接口。LinkedList实现了List接口，其内部表示形式是双向链表，因此它可以将元素插入、添加和删除的效率较高。

这里以LinkedList来实现链表结构，下面是简单的示例代码：

public class MyLinkedList {
    private Node head;  // 头结点
    private int size;   // 链表元素个数
 
    private class Node {
        private Object data; // 每个节点的数据
        private Node next;   // 每个节点指向下一个节点的引用
 
        public Node(Object data) {
            this.data = data;
        }
    }

    // 添加节点
    public void add(Object obj) {
        Node newNode = new Node(obj);
        if (head == null) {
            head = newNode;
        } else {
            Node temp = head;
            while(temp.next != null) {
                temp = temp.next;
            }
            temp.next = newNode;
        }
        size++;
    }
    
    // 删除节点
    public boolean remove(Object obj) {
        if (obj == null) {
            for(Node temp = head; temp != null; temp = temp.next) {
                if (temp.data == null) {
                    remove(temp);
                    return true;
                }
            }
        } else {
            for(Node temp = head; temp != null; temp = temp.next) {
                if (obj.equals(temp.data)) {
                    remove(temp);
                    return true;
                }
            }
        }
        return false;
    }
    
    // 获取节点数据
    public Object get(int index) {
        rangeCheck(index);
        Node temp = head;
        for(int i = 0; i < index; i++) {
            temp = temp.next;
        }
        return temp.data;
    }
    
    // 更新节点数据
    public void set(int index,Object obj) {
        rangeCheck(index);
        Node temp = head;
        for(int i = 0; i < index; i++) {
            temp = temp.next;
        }
        temp.data = obj;   
    }
    
    // 返回链表元素个数
    public int size() {
        return size;
    }
    
    // 判断链表是否为空
    public boolean isEmpty() {
        return size == 0;
    }
    
    // 确保下标不越界
    private void rangeCheck(int index) {
        if (index >= size) {
            throw new IndexOutOfBoundsException("Index:" + index + ", Size:" + size);
        }
    }
    
    // 删除节点并更新链表元素个数
    private void remove(Node node) {
        if (node == head) {
            head = head.next;
        }
        else {
            node.next = node.next.next;
        }
        size--;
    }
}

二、Java链表基本操作

1. 添加操作

链表的添加操作分为两种情况：

• 添加到链表头部

public void addFirst(E e) {
    Node<E> newNode = new Node<>(e);
    newNode.next = head;
    head = newNode;
    size++;
}
    

• 添加到链表尾部

public void addLast(E e) {
    Node<E> newNode = new Node<>(e);
    if (head == null) {
        head = newNode;
    } else {
        Node<E> node = head;
        while (node.next != null) {
            node = node.next;
        }
        node.next = newNode;
    }
    size++;
}
    

2. 删除操作

链表的删除操作也分为两种情况：

• 删除头部元素

public E removeFirst() {
    if (head == null) {
        return null;
    }
    Node<E> oldHead = head;
    head = head.next;
    size--;
    return oldHead.data;
}
    

• 删除尾部元素

public E removeLast() {
    if (head == null) {
        return null;
    }
    Node<E> node = head;
    if (node.next == null) {
        head = null;
        size--;
        return node.data;
    }
    while (node.next.next != null) {
        node = node.next;
    }
    Node<E> oldNode = node.next;
    node.next = null;
    size--;
    return oldNode.data;
}
    

三、Java链表元素访问

链表元素的访问可以通过下标方式和迭代器方式实现。

1. 下标方式

public E get(int index) {
    if (index < 0 || index >= size) {
        throw new IndexOutOfBoundsException();
    }
    Node<E> node = head;
    for (int i = 0; i < index; i++) {
        node = node.next;
    }
    return node.data;
}

2. 迭代器方式

public Iterator<E> iterator() {
    return new LinkedIterator();
}
private class LinkedIterator implements Iterator<E> {
    private Node<E> node = head;
    public boolean hasNext() {
        return node != null;
    }
    public E next() {
        if (!hasNext()) {
            throw new NoSuchElementException();
        }
        E item = node.data;
        node = node.next;
        return item;
    }
    public void remove() {
        throw new UnsupportedOperationException();
    }
}

四、Java链表性能

Java链表的插入、添加和删除操作效率较高，但在访问链表元素时，其效率较低，因为它需要按顺序访问链表中的每个元素。

与数组相比，Java链表的性能差异很大。数组在通过下标访问元素时具有较好的性能，因为它可以通过索引方便地访问元素。而链表则需要按顺序访问元素，因此访问链表元素时的效率较低。

五、总结

链表是一种常见的数据结构，Java提供了LinkedList和List接口来实现链表结构。Java链表结构具有插入、添加和删除操作效率较高等优势，但在访问链表元素时效率较低。在开发时需要根据需求选取数据结构，使得程序具有更高的性能。