单链表

2020-04-26 16:03:54来源:博客园 阅读 ()

新老客户大回馈,云服务器低至5折

单链表

   a.特点:

      1.链表是以节点方式来存储的,

      2.每个节点包含data域,next域:指向下一个节点

      3.链表的各个节点不一定是连续存放

      4.链表分带头结点的链表和不带头结点的链表

   b.内存中实际结构图:

         

  c.逻辑结构图:

       

  d.单链表实现思路:

    创建一个存储空间:

      代码实现:

package LinkedList;

public class OrderlyList {
	public int sum;
	public String name;
	public String nickName;
	public OrderlyList orderlyList;

	public OrderlyList(int sum,String name,String nickName) {
		this.sum=sum;
		this.name=name;
		this.nickName=nickName;
	}

	@Override
	public String toString() {
		return "number:"+sum+" name:"+name+" nickName:"+nickName;
	}
}

  

    添加时:

      方法一: 直接添加到链表尾部(不推荐)

      1. 先创建一个head头结点,作用就是表示单链表的头
      2. 后面每添加一个节点,就直接加入到链表的最后

            (1) 先定义一个头结点,头结点不能动,不存放具体的数据

            (2) 添加节点到单向链表

                1> 找到当前链表的最后节点

                2> 将最后这个节点的next 指向新的节点

                3>通过一个辅助遍历,帮忙遍历整个链表

代码实现:

 1 class Init{
 2     //初始化
 3     OrderlyList head =  new OrderlyList(0,"","");
 4     public void add(OrderlyList record) {
 5         //初始化一个临时变量
 6         OrderlyList temp = head;
 7         while (true) {
 8             //判断是否到达最后一个位置
 9             if (temp.orderlyList == null) {
10                 temp.orderlyList = record;
11                 break;
12             }
13             temp = temp.orderlyList;
14         }
15     }
16     public void show() {
17         OrderlyList temp = head.orderlyList;
18         while (true) {
19             if (head.orderlyList==null) {
20                 System.out.println("是空的");
21                 return;
22             }
23             if (temp==null) {
24                 return;
25             }
26             System.out.println(temp);
27             temp = temp.orderlyList;
28             
29         }
30     }
31 }

 

      方法二: 根据编号插入链表,如果有则添加失败并给出提示

        图解:

          

      1. 找到新添加节点的位置,是通过辅助变量
      2. 让新的节点.orderlyList= temp.orderlyList
      3. temp.orderlyLis = 新的节点

代码实现:

void add(OrderlyList orderlyList) {
		OrderlyList temp = orderly;
		boolean flag = false;
		while (true) {
			if (temp.orderlyList == null) {
				break;
			}
			if (temp.orderlyList.sum > orderlyList.sum) {
				break;
			}
			if (temp.orderlyList.sum == orderlyList.sum) {
				flag = true;
			}
			temp = temp.orderlyList;
		}
		if (!flag) {
			orderlyList.orderlyList = temp.orderlyList;
			temp.orderlyList = orderlyList;
		} else {
			System.out.println("已经存在");
		}
	}

  

 修改时:   

    根据编号来修改,但编号不能更改,否则相当与添加

代码实现:

	//	修改
	void update(OrderlyList list) {
		OrderlyList temp = orderly.orderlyList;
		boolean flag = false;
		while (true) {
			if (temp == null) {
				break;
			}
			if (temp.orderlyList.sum == list.sum) {
				flag = true;
				break;
			}
			temp = temp.orderlyList;
		}
		if (flag) {
			temp.orderlyList.name = list.name; 
			temp.orderlyList.nickName = list.nickName;
			temp.orderlyList.orderlyList =list.orderlyList;
		}
	}

  

  删除时:

     图解:

      

代码实现:

// 删除
	void delect(int sum) {
		OrderlyList temp = orderly.orderlyList;
		boolean flag = false;
		while (true) {
			if (temp == null) {
				break;
			}
			if (temp.orderlyList.sum == sum) {
				flag = true;
				break;
			}
			if (temp.orderlyList.sum > sum) {
				break;
			}
			temp = temp.orderlyList;
		}
		if (flag) {
			temp.orderlyList = temp.orderlyList.orderlyList;
		}
	}
    1. 找到需要删除的节点的前一个节点
    2. temp.orderlyList = temp.orderlyList.orderlyList;
    3. 被删除的节点会因为没有指向从而会被垃圾回收机制回收;

原文链接:https://www.cnblogs.com/liaozhongxing/p/12783285.html
如有疑问请与原作者联系

标签:

版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有

上一篇:Java 虚拟机中的运行时数据区分析

下一篇:Java面试小tip精华汇总篇「最新版」