单链表

概述

单链表是一种链式存取的数据结构，用一组地址任意的存储单元存放线性表中的数据元素。链表中的数据是以结点来表示的。

每个结点的构成：

• 元素(数据元素的映象)
• 指针(指示后继元素存储位置)

元素就是存储数据的存储单元， 指针就是连接每个结点的地址数据。

单链表结构图

结点类

/** * @auther: lawt * @date: 2018/11/4 08 * @Description: 结点信息 */ public class Node { /** * 为了方便，这两个变量都使用public，而不用private就不需要编写get、set方法了。 * 存放数据的变量，简单点，直接为int型 */ public int data; /** * 存放结点的变量,默认为null */ public Node next; /** * 构造方法，在构造时就能够给data赋值 */ public Node(int data) { this.data = data; } }

相关操作

插入头结点

public static void insertHead(Node head, Node newHead) { Node old = head; head = newHead; head.next = old; }

插入尾节点

public static void insertTail(Node tail, Node newTail) { Node old = tail; tail = newTail; tail.next = null; old.next = tail; }

遍历

public static void query(Node head) { while (head != null) { System.out.print(head.data + " "); head = head.next; } System.out.println(); }

查找某个结点

public static int find(Node head, int data) { int index = -1;//初始值为-1 int count = 0;//可以知道循环次数 while (head != null) {//当头结点部位null if (head.data == data) {//如果该节点的值==找的 index = count; } count++;//没有找到，循环次数+1 head = head.next;//没有找到继续遍历 } return index;//返回链表下标

插入

public static void insert(Node pre, Node node) { node.next = pre.next; pre.next = node; }

删除

public static void delete(Node pre) { pre.next = pre.next.next; }

获取中间节点

public static Node getMid(Node head) { if (head == null) { return head; } Node fast = head; Node slow = head; while (fast.next != null && fast.next.next != null) { slow = slow.next; fast = fast.next.next; } return slow;

反转链表

public static Node reversal(Node head) { Node pre = null; Node next = null; while (head != null) { next = head.next; head.next = pre; pre = head; head = next; } return pre; }

测试代码

public static void main(String[] args) { Node node1 = new Node(1); Node node2 = new Node(2); Node node3 = new Node(3); Node node4 = new Node(4); node1.next = node2; node2.next = node3; node3.next = node4; node4.next = null; query(node1); Node newHead = new Node(6); insertHead(node1, newHead); Node node7 = new Node(7); insertTail(node4, node7); query(newHead); System.out.println(find(newHead, 3)); Node node8 = new Node(8); insert(node3, node8); query(newHead); delete(newHead, node3); query(newHead); Node head= new Node(1); Node n2 = new Node(2); Node n3 = new Node(3); head.next = n2; n2.next = n3; n3.next = null; System.out.println(getMid(head).data); System.out.println(); Node node = reversal(head); while (node != null) { System.out.print(node.data + " "); node = node.next; } }

结果