链表
由指针把若干个结点连接成链状结构,是动态数组。创建时无需知道链表长度,每增加一个结点,就分配一次内存空间,所以无闲置空间,空间利用率要比数组高。但如果想找第i个结点,只能根据结点指向,沿着指向一个一个结点找,所以链表的时间复杂都为O(n)。。
- 定义一个单链表结点。Java以一个类作为一个结点
class ListNode{
int data; //数据域
ListNode next; //指针域
}
- 单链表尾部增加结点,带头结点。(尾插法)
//尾插法
public void add(ListNode node){
//空链表,直接插入
if(team == null){
team.next = node;
}
//链表不为空,则将辅助指针移到最后一个结点
while(true){
if(team.next == null){
break; //此时已经遍历到最后一个结点
}
team = team.next; //如果链表下一结点不为空,则指针下移一个结点
}
team.next = node; //将结点插入
}
- 单链表删除结点
public void del(int data){
//空链表
if (head.next == null) {
return;
}
HeroNode team = head; //辅助指针
boolean flag = false; //标识是否找到待删除结点
while (true) {
if (team.next == null) {
break;
}
if (team.next.data == data) {
flag = true;
break;
}
team = team.next;
}
if (flag) {
team.next = team.next.next;
} else {
System.out.println("未找到需要删除结点");
}
}
- 单链表的遍历
public void show(){
HeroNode team = head;
while (true) {
if (team.next == null) {
break;
}
team = team.next;
System.out.println(team);
}
}