1. 介绍
链表是有序的列表，但是它在内存中是存储如下
小结:
(1)链表是以节点的方式来存储,是链式存储
(2)每个节点包含 data 域， next 域：指向下一个节点.
(3)如图：发现链表的各个节点不一定是连续存储.
(4)链表分带头节点的链表和没有头节点的链表，根据实际的需求来确定
2. 思路a 在链表尾部添加节点
(1). 用temp变量从head节点开始，遍历。找到temp.next为空的位置。
(2) 把新节点放到temp.next位置
b 按照顺序加入节点
(1) 用temp从head开始遍历，找到temp.next的data的数值刚好大于要插入的节点的数值
(2) 新节点.next指向 temp.next
,
c. 单链表删除一个节点(1). 我们先找到 需要删除的这个节点的前一个节点 temp
(2). temp.next = temp.next.next
(3). 被删除的节点，将不会有其它引用指向，会被垃圾回收机制回收
d. 更改一个节点的信息(1) .把链表的其中一个节点的信息改为外界的一个节点的信息
(2). temp从head.next开始遍历，因为head是哑节点，没有数据。遍历单链表的节点，比较链表的data的数值是否的等于外界的节点的data的值。
(3) 找到后，把外界节点的所有信息赋给temp节点
3. 代码实现一个节点的代码
public class Node {
@Override
public String toString() {
return "Node [no=" + no + ", name=" + name + "]";
}
public int no;
public String name;
public Node next;
//构造器
Node(int no,String name){
this.no=no;
this.name=name;
}
}
单链表
public class SingleLinkedList {
//初始化头节点，不存放具体的数据
private Node head=new Node(0,"");
//添加节点到链表
//找最后节点，将最后节点的next域指向新来的节点
//谁的nex==null，就加到谁的后面
public void add(Node newNode) {
//temp指向哑节点head
Node temp=head;
while(true) {
//找到链表的最后
if(temp.next==null) {
break;
}
temp=temp.next;
}
//最后链表的next指向newNode
temp.next=newNode;
}
public void update(Node newNode) {
//判断是否为空
if(head.next==null) {
System.out.println("链表为空");
return;
}
//找到要修改的节点，根据no编号
//定义辅助变量
Node temp=head.next;
boolean flag=false;
while(true) {
if(temp==null) {
break;
}
if(temp.no==newNode.no) {
flag=true;
break;
}
temp=temp.next;
}
if(flag) {
temp.no=newNode.no;
temp.name=newNode.name;
}else {
System.out.printf("没有找到编号 %d 的节点,不能修改n",newNode.no);
}
}
public void del(int no) {
//指向哑节点，因为有可能删除第1个
Node temp=head;
boolean flag=false;
while(true) {
if(temp.next==null) {
break;
}
if(temp.next.no==no) {
flag=true;
break;
}
temp=temp.next;
}
if(flag) {
temp.next=temp.next.next;
}else {
System.out.printf("没有节点%dn",no);
}
}
//遍历链表
public void list() {
//判断链表是否为空
if(head.next==null) {
System.out.println("链表为空");
return;
}
//head是哑节点，head.next才是真正意义上的first
for(Node x=head.next;x!=null;x=x.next) {
System.out.println(x);
}
}
//第二种方式添加英雄时，根据排名将英雄插入指定位置
//如果有这个排名，刚添加失败，并给出提示
public void addByOrder(Node newNode) {
//头节点不能动
//单链表 找的temp位于添加的前1个节点
Node temp=head;
boolean flag=false; //添加的符号是否存在，默认为false
while(true) {
//temp已经到了最后一个节点
if(temp.next==null) {
break;
}
//找到temp.next刚好大于newNode
if(temp.next.no>newNode.no) {
break;
}
//说明要添加的Node的编号已经存在了
else if(temp.next.no==newNode.no) {
flag=true; //说明编号已经存在
break;
}
//后移遍历当前链表
temp=temp.next;
}
//判断flag的值
if(flag) {
//不能添加
System.out.printf("准备插入的节点%d已经存在了，不能加入n",newNode.no);
}else {
//插入到链表中
newNode.next=temp.next;
temp.next=newNode;
}
}
public static void main(String[] args) {
Node n1=new Node(1,"宋江");
Node n2=new Node(2,"孙悟空");
Node n3=new Node(3,"唐僧");
Node n4=new Node(4,"沙师弟");
SingleLinkedList li=new SingleLinkedList();
// li.add(n1);
// li.add(n4);
// li.add(n2);
// li.add(n3);
li.addByOrder(n1);
li.addByOrder(n4);
li.addByOrder(n2);
li.addByOrder(n3);
li.addByOrder(n3);
System.out.println("------");
//遍历数组
li.list();
Node nn=new Node(4,"沙僧");
li.update(nn);
System.out.println("-------修改第4号节点");
li.list();
System.out.println("-----删除两个节点-----");
li.del(1);
li.del(4);
li.list();
}
}
运行结果
