数据结构与算法：Java实现链表、队列等基本操作

原创绝地灬酷狼 2024-11-08 16:18 0阅读 0赞

在Java中实现链表、队列等基本数据结构，你可以使用以下代码作为参考。这里我将提供单链表和循环队列的简单实现。

###单链表单链表是一种线性数据结构，其中每个元素包含数据部分和指向下一个元素的指针。

```javapublic class ListNode {
int val;
 ListNode next;
 ListNode(int x) { val = x; }
}

public class LinkedList {
 private ListNode head;

public LinkedList() {
 head = null;
 }

// 在链表头部添加元素 public void addFirst(int val) {
 ListNode newNode = new ListNode(val);
 newNode.next = head;
 head = newNode;
 }

// 在链表尾部添加元素 public void addLast(int val) {
 ListNode newNode = new ListNode(val);
if (head == null) {
 head = newNode;
} else {
 ListNode current = head;
 while (current.next != null) {
 current = current.next;
 }
 current.next = newNode;
 }
 }

//从链表中移除元素 public void remove(int val) {
 ListNode current = head;
 ListNode prev = null;
 while (current != null) {
if (current.val == val) {
if (prev == null) {
 head = current.next;
} else {
 prev.next = current.next;
 }
 return;
 }
 prev = current;
 current = current.next;
 }
 }

//打印链表 public void printList() {
 ListNode current = head;
 while (current != null) {
 System.out.print(current.val + " -> ");
 current = current.next;
 }
 System.out.println("null");
 }
}
```###循环队列循环队列是一种使用固定大小数组实现的队列，其中队列的头和尾可以“环绕”数组的末端。

```javapublic class CircularQueue {
 private int[] arr;
 private int front, rear, size, capacity;

public CircularQueue(int capacity) {
 this.capacity = capacity;
 this.size =0;
 front =0;
 rear = -1;
arr = new int[capacity];
 }

//入队 public boolean enqueue(int item) {
if (size == capacity) {
 return false;
 }
if (rear == capacity -1) {
 rear = -1;
 }
arr[rear +1] = item;
 rear = rear +1;
 size++;
 return true;
 }

//出队 public int dequeue() {
if (size ==0) {
 return -1;
 }
int item = arr[front];
 front = (front +1) % capacity;
 size--;
 return item;
 }

// 查看队首元素 public int peek() {
if (size ==0) {
 return -1;
 }
 return arr[front];
 }

//检查队列是否为空 public boolean isEmpty() {
 return size ==0;
 }

//检查队列是否已满 public boolean isFull() {
 return size == capacity;
 }
}
```这些代码提供了链表和循环队列的基本操作，包括添加、删除、查看元素等。你可以根据需要进一步扩展这些类，添加更多的功能和异常处理。