数据结构实现：Java中链表、队列等设计

原创桃扇骨 2024-09-11 16:54 102阅读 0赞

在Java中，我们可以使用多种方式来实现链表和队列。以下是两种基本数据结构的设计：

1. 链表（LinkedList）：

```java
// 定义链表节点
class Node {
    int data; // 数据
    Node next; // 指向下一个节点的引用

// 构造函数
    Node(int item) {
        data = item;
        next = null;
    }
}

// 链表类，包含添加元素、删除元素等方法
class LinkedList {
    Node head; // 链表头节点

// 添加元素到链尾
    void appendNode(int new_data) {
        Node newNode = new Node(new_data);
        
        if (head == null) { // 如果链表为空
            head = newNode;
            return;
        }
        
        // 遍历链表找到最后一个节点
        Node lastNode = head;
        while (lastNode.next != null) {
            lastNode = lastNode.next;
        }

lastNode.next = newNode; // 将新节点连接到链尾
    }

// 删除给定值的元素（如果存在）
    void deleteNode(int key) {
        if (head == null) { // 如果链表为空，直接返回
            return;
        }
        
        Node current = head;
        while (current != null && current.data != key) {
            current = current.next;
        }

// 如果找到了要删除的元素
        if (current != null) {
            // 将当前节点的下一个节点指向前一个节点
            current.next = current.next == null ? null : current.next.next;

// 链表头部更新，如果被删除的是头节点
            head = current.next == null ? head : current.next;
        }
    }

// 获取链表的长度（节点数量）
    int length() {
        int count = 0;
        Node currentNode = head;

while (currentNode != null) {
            count++;
            currentNode = currentNode.next;
        }

return count;
    }
}
```

2. 队列（Queue）：

Java中，队列通常实现为`ArrayList`的子类。这里我们创建一个基础的`Queue`接口和一个基于`ArrayList`的实现：

```java
// 队列接口
interface Queue {
    // 添加元素到队尾
    void enqueue(int data);

// 从队头移除并返回元素（如果存在）
    int dequeue() throws EmptyQueueException;

// 检查队列是否为空
    boolean isEmpty();
}

// 基于ArrayList的队列实现
class QueueImplementation implements Queue {
    private ArrayList<Integer> elements = new ArrayList<>();

@Override
    public void enqueue(int data) {
        elements.add(data);
    }

@Override
    public int dequeue() throws EmptyQueueException {
        if (isEmpty()) {
            throw new EmptyQueueException();
        }
        
        return elements.remove(0);
    }

@Override
    public boolean isEmpty() {
        return elements.isEmpty();
    }
}
```

以上是链表和队列的基本实现，实际使用时可能需要根据具体需求进行扩展。