1.单链表节点需要一个next指针
class Node {
public int data; //节点中存在数值data
public Node next;//节点中存在下一个节点的引用(地址),此处可能有疑问是next的类型,下面着重分享一下
public Node(int data) {//构造方法,在实例化对象时给对象进行初始化
this.data = data;//this.next会被默认为null
}
}
2.带头单链表
class MyLinkedList {
public Node head;//head为对第一个节点的引用
//1.头插法
public void addFirst(int data) {
Node node = new Node(data);//我们先把要插的数据造成链表再进行插入
Log.d("MyLinkedList", "addFirst() node =" + node.hashCode());
if (this.head == null) {//一个数据也没有时,其实就是直接存入一个数据
this.head = node;//然后将head指向我们刚刚创建的节点
return;//完成后记得直接返回
}
node.next = this.head;//注意两者不能颠倒顺序(自己可以尝试一下如果颠倒链表将接不上),节点都是先连接才能保证链表的连接
this.head = node;
}
//2.尾插法
public void addLast(int data) {
Node node = new Node(data);
if (this.head == null) {//如果链表为空,直接插入
this.head = node;
return;
}
Node cur = this.head;//创建cur用来表示目前节点
while (cur.next != null)//设置循环让cur往后走,当cur到最后一个节点时停止循环
{
cur = cur.next;//cur后移
}
cur.next = node;//最后一个节点接上尾巴
}
//指定位置插入
public void addIndex(int index, int data) {
if (index == 0) {//空链表直接插
this.addFirst(data);
return;
}
if (index == this.size()) {//this.size()返回链表长度,位置为最后,直接调用尾插法
this.addLast(data);
return;
}
Node cur = searchIndex(index);//返回目标位置的前一个位置的节点
Node node = new Node(data);//为该数据创立节点
node.next = cur.next;//以下两步完成连接,一般都是先接上后边,如果这两步顺序调换,则无法完成连接
cur.next = node;
}
private Node searchIndex(int index) {//封装一个方法用来找指定位置
if (index < 0 || index > this.size())//判断位置合法性
{
throw new RuntimeException("index位置不合法");
}
Node cur = this.head;
int count = 0;
while (count != index - 1)//找到指定位置的前一个位置,返回这个节点
{
count++;
cur = cur.next;
}
return cur;
}
//3.打印单链表
public void display() {
Node cur = this.head;
while (cur != null) {//设置循环遍历链表 完成打印
System.out.println(cur.data + " ");
Log.d("MyLinkedList", "display() =" + cur.data + " ");
cur = cur.next;
}
}
//4.得到单链表的长度
public int size() {
int count = 0;
Node cur = this.head;
while (cur != null) {//遍历链表,求出长度,返回长度
count++;
cur = cur.next;
}
return count;
}
//6.查找是否包含关键字key是否在单链表当中
public boolean contains(int key) {
return false;
}
//7.删除第一次出现关键字为key的节点
public void remove(int key) {
}
//8.删除所有值为key的节点
public void removeAllKey(int key) {
}
//9.清空链表
public void clear() {
}
}
2.链表翻转
// 1、递归反转
// 递归反转法在反转当前节点之前先反转后续节点。
// 这样从头结点开始,层层深入直到尾结点才开始反转指针域的指向。
// 简单的说就是从尾结点开始,
public Node reverse(Node head) {
if (head == null || head.next == null) {
return head;
}
Node pre = reverse(head.next);
head.next.next = head;
head.next = null;
return pre;
}
public static Node reverse2(Node head) {
if (head == null || head.next == null) {
return head;
}
Node pre = null;
Node next;
while (head != null) {
next = head.next;
head.next = pre;
pre = head;
head = next;
}
return pre;
}