java 数据结构单链表的实现

Java中实现单链表数据结构通常需要以下几个步骤：

1. 定义节点类

首先需要定义一个节点类，用于表示链表中的一个节点。每个节点包含两个属性：data表示节点的数据，next表示节点的下一个节点。这两个属性都需要定义为public，以便后续操作的访问。

public class Node {
  public int data;
  public Node next;

  public Node(int data) {
    this.data = data;
    this.next = null;
  }
}

2. 定义链表类

接下来需要定义一个链表类，用于对节点进行管理。链表类需要包含两个属性：head表示链表的头节点，size表示链表中节点的数量。

public class LinkedList {
  public Node head;
  public int size;

  public LinkedList() {
    head = null;
    size = 0;
  }
}

3. 实现插入操作

插入操作常见有三种：在头部插入、在尾部插入、在指定位置插入。具体实现方式如下：

在头部插入

在头部插入可以通过以下代码实现：

public void insertAtHead(int data) {
  Node newNode = new Node(data);
  newNode.next = head;
  head = newNode;
  size++;
}

在尾部插入

在尾部插入可以通过以下代码实现：

public void insertAtTail(int data) {
  Node newNode = new Node(data);
  if (head == null) {
    head = newNode;
  } else {
    Node currentNode = head;
    while (currentNode.next != null) {
      currentNode = currentNode.next;
    }
    currentNode.next = newNode;
  }
  size++;
}

在指定位置插入

在指定位置插入可以通过以下代码实现：

public void insertAtIndex(int index, int data) {
  if (index < 0 || index > size) {
    throw new IndexOutOfBoundsException("Invalid index");
  }
  if (index == 0) {
    insertAtHead(data);
  } else if (index == size) {
    insertAtTail(data);
  } else {
    Node currentNode = head;
    for (int i = 1; i < index; i++) {
      currentNode = currentNode.next;
    }
    Node newNode = new Node(data);
    newNode.next = currentNode.next;
    currentNode.next = newNode;
    size++;
  }
}

4. 实现删除操作

删除操作通常有两种：删除头部节点、删除指定位置节点。具体实现方式如下：

删除头部节点

删除头部节点可以通过以下代码实现：

public void deleteAtHead() {
  if (head != null) {
    head = head.next;
    size--;
  }
}

删除指定位置节点

删除指定位置节点可以通过以下代码实现：

public void deleteAtIndex(int index) {
  if (index < 0 || index >= size) {
    throw new IndexOutOfBoundsException("Invalid index");
  }
  if (index == 0) {
    deleteAtHead();
  } else {
    Node currentNode = head;
    for (int i = 1; i < index; i++) {
      currentNode = currentNode.next;
    }
    currentNode.next = currentNode.next.next;
    size--;
  }
}

示例说明

下面通过两个示例说明单链表的实现：

LinkedList list = new LinkedList();
list.insertAtHead(3); // 在头部插入3
list.insertAtTail(4); // 在尾部插入4
list.insertAtIndex(1, 5); // 在位置1插入5，此时链表为3->5->4
list.deleteAtIndex(1); // 删除位置1的节点，此时链表为3->4

LinkedList list = new LinkedList();
list.insertAtTail(1); // 在尾部插入1
list.insertAtIndex(1, 2); // 在位置1插入2，此时链表为1->2
list.insertAtIndex(0, 3); // 在头部插入3，此时链表为3->1->2
list.deleteAtIndex(1); // 删除位置1的节点，此时链表为3->2