前言
一、结点的定义
二、单链表的组成
三、链表的创建方法
1.头插法
2.尾插法
四、链表在指定位置插入
总结
前言
单链表是基础的数据结构，需要对其熟练掌握
一、结点的定义结点：结点由两个域组成，结点的域分为数据域和next域
data域顾名思义：存放数据的域
next域：指向下一个地址的域，相当于指针
public class HeroNode{ //定义HeroNode,对象就是下一个节点
private Object data;
public Heronode next;//指向下一个节点
//构造器
public Heronode(Object data){
this.data=data;
}
public Object getData() {
return data;
}
public void setData(Object data) {
this.data = data;
}
}
二、单链表的组成
链表用一组任意的储存单元存储线性表的数据元素。链表是一种物理存储单元上非连续，非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现
三、链表的创建方法 1.头插法图解
核心点：第一次插入时，直接头结点指向储存结点:headNode.next=Node1
第二次以后，需要将头结点的next存在一个临时变量temp中即：headNode.next=temp
再将要头结点与要插入结点相连接：headNode.next=Node2
再将temp存储的结点信息交给Node2.next :Node2.next=temp
//头插法建表
public void headcreate(Object x) {
Heronode Node = new Heronode(x);
if(headNode.next==null){//如果是第一次插入
headNode.next=Node;
}else {
Heronode temp=headNode.next;//将头节点next用临时节点储存
headNode.next=Node;//头节点指向当前节点
Node.next=temp;//当前节点指向临时节点
}
}
2.尾插法
图解
尾插实际上就是用一个临时结点进行一个遍历，当结点的next域为空时，再进行插入新结点
//尾插法建表
public void add(Object data) {
//因为headNode不能存放数据：（headNode是用来指向第一个节点的位置）
// 因为headNode不能存放数据,所以需要一个temp来辅助遍历
Heronode temp = headNode;
//遍历节点
while (true) {
if (temp.next == null) {//遍历到最后
break;
}
temp = temp.next;//如果没有找到，temp后移;
}
//当temp退出while循环时，temp就指向了最后
temp.next = new Heronode(data);//指向新节点
}
四、链表在指定位置插入
在指定位置添加，这里我定义了一个长度，用来判定此位置是否合法
之后设置一个number来指定元素，第一个元素下标就是1，根据将要插入的位置比较
当两位置相同时执行：
node.next=p.next;
p.next=node;
public void insert(int num,Object x) {
Heronode node=new Heronode(x);
int number=1;//元素下标从1开始
if (num <=0 ||num>length()) {
System.out.println("插入不合法");
return;
}
Heronode p=headNode;//设置辅助节点
while (true){
if(p.next==null){
break;
}
if(number==num){
node.next=p.next;
p.next=node;
break;
}
p=p.next;
number++;
}
}
总结
链表的结构是基础，需要多加练习，当然上面的方法中，如果你会在指定位置添加了，其他，比如说在指定位置修改元素，或者删除元素，都与这类似，链表的反转和合并也是重点，需要掌握
完整代码
public class linkList {
private Heronode headNode = new Heronode(null);
public void clear() {
headNode.next = null;
}
public boolean isEmpty() {
return headNode.next == null;
}
public void reveselist(){
if(headNode.next==null||headNode.next.next==null){
return ;
}
Heronode temp=headNode.next;
Heronode next=null;
Heronode revesenode=new Heronode(null);
while (temp!=null){
next=temp.next;//暂时储存temp的下一个指针
temp.next=revesenode.next;//将temp的下一个节点指向新链表的最前端
revesenode.next=temp;//将revesenode的下一个指针指向temp
temp=next;//temp向后移动
}
headNode.next=revesenode.next;//将头结点指向revesenode.next,实现链表反转
}
//头插法建表
public void headcreate(Object x) {
Heronode Node = new Heronode(x);
if(headNode.next==null){//如果是第一次插入
headNode.next=Node;
}else {
Heronode temp=headNode.next;//将头节点next用临时节点储存
headNode.next=Node;//头节点指向当前节点
Node.next=temp;//当前节点指向临时节点
}
}
//链表的长度
public int length() {
if (isEmpty()) {
System.out.println("链表为空");
}
int length = 0;
Heronode p = headNode;
while (true) {
if (p.next == null) {
break;
}
p = p.next;
length++;
}
return length;
}
//尾插法建表
public void add(Object data) {
//因为headNode不能存放数据：（headNode是用来指向第一个节点的位置）
// 因为headNode不能存放数据,所以需要一个temp来辅助遍历
Heronode temp = headNode;
//遍历节点
while (true) {
if (temp.next == null) {//遍历到最后
break;
}
temp = temp.next;//如果没有找到，temp后移;
}
//当temp退出while循环时，temp就指向了最后
temp.next = new Heronode(data);//指向新节点
}
public void insert(int num,Object x) {
Heronode node=new Heronode(x);
int number=1;//元素下标从1开始
if (num <=0 ||num>length()) {
System.out.println("插入不合法");
return;
}
Heronode p=headNode;//设置辅助节点
while (true){
if(p.next==null){
break;
}
if(number==num){
node.next=p.next;
p.next=node;
break;
}
p=p.next;
number++;
}
}
public void update(int num,Object x) {
Heronode node=new Heronode(x);
int number=1;//第一号元素
if (num <= 0 ||num>length()) {
System.out.println("元素位置不合法");
return;
}
Heronode p=headNode;
while (true){
if(p.next==null){
break;
}
if(number==num){
node.next=p.next.next;
p.next=node;
break;
}
p=p.next;
number++;
}
}
public void delete(int num) {
int number=0;//第一号元素
if (num <=0 ||num>length()) {
System.out.println("元素位置不合法");
return;
}
Heronode p=headNode;
while (true){
if(p.next==null){
break;
}
if(number==num){
p.next=p.next.next;
break;
}
p=p.next;
number++;
}
}
public void remove(Object x) {
if(isEmpty()){
System.out.println("链表为空");
return;
}
Heronode p=headNode;
boolean flag=false;//用于判断是否找到
while (true){//遍历链表
if(p.next==null){
break;
}
if(p.next.getData()==x){//判断当前节点的下一个节点的数据是否为这个数据
flag=true;
break;
}
p=p.next;//指针向后移
}
if(flag){
p.next=p.next.next;//当前节点的下一个节点指向下下个节点，达到删除效果
}
else
System.out.println("没有找到要删除的数据");
}
public void list1() {
//先判断链表是否为空
if (isEmpty()) {
System.out.println("链表为空");
return;
}
//因为头节点不能动，所以我们需要下一个辅助变量来遍历
Heronode temp = headNode.next;
while (true) {
if (temp.next == null) {
System.out.print(temp.getData());
break;
}
//输出节点信息
System.out.print(temp.getData() + " ");
//将节点后移
temp = temp.next;
}
}
}
欢迎分享，转载请注明来源：内存溢出
微信扫一扫
支付宝扫一扫
评论列表（0条）