链表是一系列的存储数据元素的单元通过指针串接起来形成的，因此每个单元至少有两个域，一个域用于数据元素的存储，另一个域指向其他单元的指针。这里具有一个数据域和多个指针域的存储单元通常称为结点。
模型.png
上图是一种最简单的结点结构，它是构成单链表的基本结点结构。在结点中数据域用来存储数据元素，指针域用于指向下一个结点的引用。
我们上面一直在说指针，有的人可能会有疑问在java里面不是没有指针吗？其实在java里面只是没有显示的指针类型，实际上在底层实现上还是通过指针来实现的，只是在java中使用对象的引用来替代了指针因此在使用Java实现该结点结构时，一个结点本身就是一个对象。节点的数据域data可以使用一个Object类型的对象来实现，用于存储任何类型的数据元素，但是这些数据元素必须是同一种类型，这也是单链表要注意的，然后通过对象的引用指向该元素；而指针域next可以通过节点对象的引用来实现。
废话也说得差不多了，开始搬砖：
第一个类新建数据类(这里用了一个泛型，有兴趣的可以看看泛型相关的书籍，在后面我也将会更新泛型的讲解)：
public class Node<E>{
public E data;//数据域
public Node next;//指向下个节点的引用
public Node() {//无参数构造方法
}
public Node(E data) {
this.data = data;
}
}
开始对单链表进行操作：
public class Main {
private static int length;
private static Node point;
private static Node head;//头指针
private static Node rear;//尾部指针
public static void main(String[] args) {
head = new Node();
rear = head;
length = 0;
addData(5);
// addData(8);
// insertData();
// insertFirst();
// find(45);
// deleteData(5);
traverse();
}
/**
* 从尾部插入一条元素
* @param node
*/
private static void addData(int data) {
point = new Node();
point.data = data;
rear.next = point;
rear = point;
length++;
}
/**
* 在头部插入一个元素
*/
private static void insertData() {
point = new Node();
point.data = 23;
point.next = head.next;
head.next = point;
length++;
}
/**
* 遍历输出链表
*/
public static void traverse() {
point = head; //移动临时引用到头结点
if (head != null)
System.out.print("[" + head.data + "]");
while (point.next != null) {
System.out.print("-➜[" + point.next.data + "]");
point = point.next;
}
System.out.println();
}
/**
* 插入一个新的首节点,并改变原来首节点的值（赋值）
*/
public static void insertFirst() {
point = new Node();
head.data = 45;
point.next = head;
head = point;
length++;
}
/**
* 查找方法（单链表只能从第一个节点开始依次向后查找）,和遍历输出的方法差不多
*/
public static void find(int data) {
point = head; //移动临时引用到头结点
if (head != null) {
System.out.print("[" + head.data + "]");
}
while (point.next != null) {
if(point.next.data.equals(1)) {
System.out.print("-➜[" + point.next.data + "]");
break;
}
point = point.next;
}
}
/**
* 删除方法
*/
public static void deleteData(int data) {
point = head; //移动临时引用到头结点
Node previous = point; //要删除的上一个节点
if (head != null) {
// System.out.print("[" + head.data + "]");
}
while (point.next != null) {
if(point.next.data.equals(5)) {
point = point.next;
previous.next = point.next;
System.out.print("-➜[" + point.data + "]");
}else {
previous = point.next;
point = point.next;
}
}
}
}
上面都是对于单链表的一些基本简单操作，后续我还会继续深入对单链表继续讲解，例如。。。单链表的逆向输出（本人去搜狗的面试题之一就是问的单链表的逆向输出）
网友评论