链表

由指针把若干个结点连接成链状结构,是动态数组。创建时无需知道链表长度,每增加一个结点,就分配一次内存空间,所以无闲置空间,空间利用率要比数组高。但如果想找第i个结点,只能根据结点指向,沿着指向一个一个结点找,所以链表的时间复杂都为O(n)。。

  1. 定义一个单链表结点。Java以一个类作为一个结点
class ListNode{
	int data;		//数据域
	ListNode next;	//指针域
}
  1. 单链表尾部增加结点,带头结点。(尾插法)
	//尾插法
	public void add(ListNode node){
		//空链表,直接插入
		if(team == null){
			team.next = node;
		}
		
		//链表不为空,则将辅助指针移到最后一个结点
		while(true){
			if(team.next == null){
				break; //此时已经遍历到最后一个结点
			}
			team = team.next; //如果链表下一结点不为空,则指针下移一个结点
		}
		team.next = node; //将结点插入
	}
  1. 单链表删除结点
	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("未找到需要删除结点");
		}
    }
  1. 单链表的遍历
	public void show(){
    	HeroNode team = head;
		 while (true) {
			if (team.next == null) {
				break;
			}
			team = team.next;
			System.out.println(team);
		}
    }
全部评论

相关推荐

07-17 12:07
门头沟学院 Java
勇敢牛牛不怕困难
投递OPPO等公司7个岗位
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务