(点击跳转即可哦)
java学习专栏
单链表单链表：每个节点只保存了下个节点的地址，只能从头节点开始向后遍历，这种链表结构称为单向链表，简称单链表。
我们可以把单链表 类比 为火车，火车的不同车厢之间，都是通过一个挂钩连结的，当这两个车厢脱钩后，这两个车厢就没有任何关系了。
单链表在逻辑上是连续的。
节点类是什么呢？
每个链表的节点，就好比火车的每节车厢。由若干个链表节点构成的对象就是链表
节点类
假设现在每个节点上存储一个int 的值，那么它们之间的“挂钩”是什么啊，就是它们下节车厢的地址。
class Node{
int val; //存储当前节点保存的值
Node next; //存储下一个节点的地址（若是不懂，继续看下面）
}
这些节点对象组成的一个大实体就是链表对象。
class SingleLinedList{
Node head; //头节点，
int size; //存储的节点个数
}
在实际中，用户只需要使用单链表提供的增删改查即可。链表内部节点如何连接，如何遍历等细节用户都不关心，所以链表类的成员变量设为私有的。
节点类
class Node{ //什么都没有写，属于包权限，包内可见
int val; //当前节点存储的值
Node next; //下个节点的地址
}
链表类
public class SingleLineList{
private Node head; //头节点的地址
private int size; //链表内的节点个数
}
增删改查等用户使用的方法就写在链表类的内部。
增
public void add(int val){
Node node = new Node();
node.val = val;
if(head == null){ //此时链表内部没有节点，头节点为默认值null
head = node; //将第一个添加的节点地址设为头节点
}else{ //此时链表内部已经有节点，头节点 head 不为空
//使用单链表的头插法，新添加的节点成为新的头节点，旧的头节点逻辑上排在新节点的后面
//将新添加的节点内的 next属性 写入旧的节点地址，也就是新节点未插入前的头节点地址
node.next = head;
//新的节点变为头节点
head = node;
}
//增加了一个节点
size++;
}
要注意else语句里面的顺序不能改变，否则就会丢失原先的链表头
查看链表
要注意的是，不能直接使用head来进行引用，否则遍历完一遍链表后，链表就会丢失。
public String toString(){
String ret = "";
//使用x来拷贝head保存的头节点地址，对x进行 *** 作，不会影响head
Node x = head;
while(x != null){
ret += x.val;
ret += "->";
//将保存的下个节点的地址传给x
x = x.next;
}
return ret;
}
无头链表完整代码：
package dynamic_array;
public class SingleLinkedList {
private Node head; //当前链表的头节点
private int size; //存储节点的个数
/**
* z（头节点插入）
*
* @param val
*/
public void addHead(int val) {
Node node = new Node();
node.val = val;
// if(head == null){
// head = node;
// }else { //此时链表内不为空
// //此时，head存储的是之前的头节点的地址，将上一个节点的地址传给新插入的头节点的next属性
// node.next = head;
// //将新的节点变为新的头节点
// head = node;
// }
//优化
if (head != null) { // 若链表内不为空地址，则把旧的头节点存入新节点的next
node.next = head;
}
head = node; //不管链表内空不空，都要将新插入的节点变为新的头节点
size++;
}
/**
* 在链表的index位置插入一个值val
*
* @param index
* @param val
*/
public void addIndex(int index, int val) {
if (index < 0 || index > size) { //当index == size,就是尾插
System.out.println("index位置不合法");
return;
}
if (index == 0) { //index在头部
addHead(val);
} else { //index不在头部，寻找index位置的前驱节点
Node newNode = new Node();
newNode.val = val;
Node x = head;
for (int i = 0; i < index - 1; i++) {
x = x.next;
} //x就是前驱节点
newNode.next = x.next;
x.next = newNode;
size++;
}
}
/**
* 在链表的尾部进行插入，调用前面的 addIndex 方法
*
* @param val
*/
public void addLast(int val) {
addIndex(size, val);
}
/**查询方法
*1 查询索引为 index 的元素值为多少
*索引不合法时，输出索引不合法，并返回-1
* @param index
*/
public int find(int index) {
if (pdIndexLegal(index)) { //index 合法
Node x = head;
for (int i = 0; i < index; i++) {
x = x.next;
}
return x.val;
} else {
System.out.print("index 索引不合法");
return -1;
}
}
/**
*2 查询是否包含指定值是节点，若有，返回ture,没有返回false
* @param val
* @return
*/
public boolean contains(int val){
Node x = head;
while (x != null){
if(x.val == val){
return true;
}
x = x.next;
}
return false;
}
/**
*3 查询第一个值为 val 的索引为多少
* @param val
* @return
*/
public int findOneVal(int val){
Node x = head;
int index = 0;
while (x != null){
if(x.val == val){
return index;
}
x = x.next;
index++;
}
return -1;
}
/** 修改方法
* 修改索引值为 index 的节点值为 val
* @param index
* @param val
*/
public void set(int index, int val){
if(pdIndexLegal(index)){
Node x = head;
for (int i = 0; i < index; i++) {
x = x.next;
}
x.val = val;
}else {
System.out.println("index不合法");
}
}
/**删除方法
* 1 删除索引为index 位置的元素,
* @param index
*/
public boolean delIndex(int index){
if(pdIndexLegal(index)){
if(index == 0){
Node x = head;
head = head.next;
x.next = null;
size--;
return true;
}else{
Node x = head;
for (int i = 0; i < index-1; i++) {
x = x.next;
}//x 就是index的前驱节点
Node indexNode = x.next;
x.next = indexNode.next;
indexNode.next = null;
size--;
return true;
}
}
System.out.println("索引不合法");
return false;
}
/**
* 2 删除第一个值为 val 的元素
* @param val
* @return
*/
public boolean delOneval(int val){
if(findOneVal(val) != -1){
int index = findOneVal(val);
if(index == 0){
Node x = head;
head = head.next;
x.next = null;
size--;
return true;
}else {
Node x = head;
for (int i = 0; i < index-1; i++) {
x = x.next;
}
Node nextNode = x.next;
x.next = nextNode.next;
nextNode.next = null;
return true;
}
}else {
System.out.println("没有这个值");
return false;
}
}
// public boolean delOneVal(int val){
// if(head == null){
// System.out.println("链表为空");
// return false;
// }
// if(head.val == val){
// Node x = head;
// head = head.next;
// x.next = null;
// size--;
// return true;
// }else{ //头节点元素不是val
// Node x = head;
// while(x.next != null){ //此节点后面还有节点
// if(x.next.val == val){
// Node nextNode = x.next;
// x.next = nextNode.next;
// nextNode.next = null;
// size--;
// return true;
// }
// x = x.next;
// }
// System.out.println("没有val这个数");
// return false;
// }
// }
/**
* 3 删除链表中所有值为 val 的元素
* @param val 要删除的值
* @return 返回boolean
*/
public boolean delAllVal(int val){
if(findOneVal(val) == -1){
System.out.println("链表中没有这个值");
return false; // 表示 链表中没有这个元素
}
while(head != null && head.val == val){
Node x = head;
head = head.next;
x.next = null;
size--;
}
if(head == null){
return true;
}else{
Node x = head;
while (x.next != null){
if(x.next.val == val){
// Node nextNode = x.next;
// x.next = nextNode.next;
// nextNode.next = null;
x.next = x.next.next;
size--;
}else {
x = x.next;
}
}
return true;
}
}
/**
* 4 删除第一个链表的元素
* @return 返回一个boolean ,删除成功返回 true
*/
public boolean delfirst(){
return delIndex(0);
}
/**
* 5 删除链表的最后一个元素
* @return 返回一个boolean ,删除成功返回 true
*/
public boolean dellast(){
return delIndex(size-1);
}
/**
* 判断index是否合法，
* @param index
* @return
*/
private boolean pdIndexLegal(int index){
if(index < 0 || index >= size){
return false;
}
return true;
}
@Override
public String toString() {
String ret = "";
Node x = head;
while (x != null){
ret += x.val;
ret += "->";
x = x.next;
}
ret += null;
return ret;
}
/**
* 查看链表
*/
public void show(){
System.out.println(this); //指向了toString
}
}
/**
* 节点类
*/
class Node{
int val; //当前节点存储的值
Node next; //存储下一个节点的地址
public Node(){}
public Node(int val){
this.val = val;
}
public Node(int val, Node next) {
this.val = val;
this.next = next;
}
}
欢迎分享，转载请注明来源：内存溢出
微信扫一扫
支付宝扫一扫
评论列表（0条）