今日学习内容：链表练习
一、什么是链表？
下面有三张图，分别是链表单元——结点、链表概念和链表实际模型。
结点由两部分组成，第一部分用于存储数据，第二部分是本结点的下一个结点。这样就形成了一个递归的结构，直到最后一个结点为空时结束递归。根据这种结构的数据模型，于是就有了链表概念和链表实际模型。
这里有一个值得注意的点在于，头结点是否应该存数据，存与不存其实对链表没有太大的影响，只需注意访问位置时的实际循环次数判断。
链表基本操作：
- 删除链表（初始化链表）（赋空）（删除头结点）
- 在链表尾部添加结点
- 在任意位置添加结点（插入）
- 删除尾部结点
- 删除任意位置结点
- 查询目标结点位置
代码示例：
Node类（单击展开）
public class Node {
private Integer data;
private Node next;
public Integer getData() {
return data;
}
public void setData(Integer data) {
this.data = data;
}
public Node getNext() {
return next;
}
public void setNext(Node next) {
this.next = next;
}
public Node() {
}
public Node(Integer data, Node next) {
this.data = data;
this.next = next;
}
@Override
public String toString() {
return "Node{" +
"data=" + data +
", next=" + next +
'}';
}
}
链表方法（单击展开）
public class SuperLinked {
// 链表的长度
private int size;
// 链表的第一个结点
private Node first;
// 链表的最后一个结点
private Node last;
// 把数组添加到链表的尾部
public boolean add(Integer data) {
// 把传入的数据构建成一个结点
Node node = new Node(data, null);
// 如果现在链表是空的，那我就是第一个结点
if ( first == null ) {
first = node;
} else {
// 如果链表不是空，那我就是最后一个结点
// 我应该是在原来的last结点后面
// 我是原来last结点的下一个结点
last.setNext(node);
}
last = node;
size++;
return true;
}
public Node getNode(int index) {
if ( index < 0 ) {
index = 0;
}
if ( index >= size - 1 ) {
index = size - 1;
}
// 找到第index个
Node cursor = first;
for (int i = 0; i < index; i++) {
cursor = cursor.getNext();
}
return cursor;
}
public boolean inputNode(int index, Integer data) {
if ( getNode(index) == null ) return false;
if ( getNode(index) != null ) {
Node nodeN = new Node(data, getNode(index - 1));
getNode(index - 2).setNext(nodeN);
size++;
}
return true;
}
public boolean removeLast() {
if ( getNode(0) == null ) {
return false;
} else if ( size == 1 ) {
first = null;
size--;
} else if ( getNode(0) != null ) {
getNode(size - 2).setNext(null);
last = getNode(size - 2);
size--;
}
return true;
}
public boolean rewriteData(int index, Integer data) {
getNode(index).setData(data);
return true;
}
public int getSize() {
return size;
}
}
测试类（单击展开）
public class Demo {
public static void main(String[] args) {
SuperLinked superLinked = new SuperLinked();
superLinked.add(1);
superLinked.add(2);
superLinked.add(3);
superLinked.inputNode(2,25);
superLinked.removeLast();
System.out.println(superLinked.getNode(0));
}
}
一些思考：
数据结构的核心在于理解这些结构的创建和存在方式，然后再慢慢理解方法是如何完成的。
在理解的过程中需要记录方法名和方法作用，这样在遇到方法内调用方法时才能更快反应过来。
要善于总结，例如在学习这些数据结构时，我们会发现基本方法内容无外乎增删改查，偶尔出现特殊方法需要加以记忆。
要有耐心，这些数据结构确实构造难以理解且方法繁多，需要看到末尾甚至多次看完才可能有所理解。
原创文章，作者：254126420，如若转载，请注明出处：https://blog.ytso.com/276958.html