logo资料库

Java之单链表篇！！！ （无头单向非循环链表实现打印、头插、尾插、任意插入、查找、删除某一关键字、删除所有所选关键字、清空单链....pdf

发布时间：2022-05-29 发布人：admin 分类：说明书 资料大小：1.90M 资料格式：pdf 举报 版权申诉
第1页 / 共11页
第2页 / 共11页
第3页 / 共11页
第4页 / 共11页
第5页 / 共11页
第6页 / 共11页
第7页 / 共11页
第8页 / 共11页
资料共11页，剩余部分请下载后查看
    Java之单链表篇！！！ 之单链表篇！！！ （无头单向非循环链表实现打印、头插、尾插、任意插 （无头单向非循环链表实现打印、头插、尾插、任意插 入、查找、删除某一关键字、删除所有所选关键字、清空单链表等基本操作） 入、查找、删除某一关键字、删除所有所选关键字、清空单链表等基本操作） 单链表代码虽然不太难但是逻辑思维较强。 单链表代码虽然不太难但是逻辑思维较强。 首先对单链表的结构进行介绍，单链表是由很多个节点一个接一个串接起来的，每个节点包含两部分，数据部分和地址部分，我们这里讲的是无头的单链表，所以没 首先对单链表的结构进行介绍，单链表是由很多个节点一个接一个串接起来的，每个节点包含两部分，数据部分和地址部分，我们这里讲的是无头的单链表，所以没 有头节点，每个节点存储的是本身的数据和下一个节点的地址。 有头节点， 每个节点存储的是本身的数据和下一个节点的地址。 如图，每个节点对应下面的地址。那第一个节点的地址设置为0x111，节点中存储的数据为1，存储的下一个节点的地址为0x22，直到最后一个节点因为后面没有节 点了所以存储的地址为null（空）。 对于单链表的操作具体有以下一些步骤，（单链表是一种类型，也是由一个一个的节点构成，所以我们在进行所有的操作的时候，首先定义一个节点类，这类呢要包 对于单链表的操作具体有以下一些步骤，（单链表是一种类型，也是由一个一个的节点构成，所以我们在进行所有的操作的时候，首先定义一个节点类，这类呢要包 括图上所示的数据、next两个属性，注： 括图上所示的数据、 两个属性，注：next保存地址，所以是一个引用） 保存地址，所以是一个引用） 定义的定义的Node模板如下，整个单链表都是由一个一个的 模板如下，整个单链表都是由一个一个的Node节点串接在一起 节点串接在一起 刚开始的单链表是没有任何数据的，就像是一张白纸什么也没有，也没有地址，所以随用随插。
    1、、 单链表的打印 单链表的打印 首先定义一个引用类型cur，使其等于 首先定义一个引用类型 为空，打印完最后一个节点。 为空，打印完最后一个节点。 ，使其等于head，这时，这时cur就指向了第一个节点，那 就指向了第一个节点，那cur=cur.next是把第一个节点中存储的第二个节点的地址赋给 是把第一个节点中存储的第二个节点的地址赋给cur，以此类推直到 ，以此类推直到cur 拿上图举例。第一个节点的地址为0x111，head指向第一个节点的地址，使cur=head后cur中就是0x111第一个节点的地址，cur.next此时为0x222就是第二个节点的 地址，cur=cur.next，就是将第二个节点的地址放入cur，此时cur中为0x222，以此类推直到cur中为空。 public void disPlay(){ Node cur = this.head; while(cur!=null){ System.out.print(cur.getData()+" "); cur = cur.getNext(); } } 2、头插法 、头插法 头插法， 头插法，首先首先利用构造方法 现在指向新的第一个节点。 现在指向新的第一个节点。 利用构造方法new一个新的节点， 一个新的节点，之后呢之后呢将原来的第一个定义为 将原来的第一个定义为head的节点的地址放到刚刚新的节点的 的节点的地址放到刚刚新的节点的next中，中，然后然后 使原来指向第一个节点的 使原来指向第一个节点的head，，
    由上图的例子，新建一个节点node地址为地址为0x456，里面的数据为 由上图的例子，新建一个节点 现在的新节点指向原来的第一个节点，之后让原来指向第一个节点的head现在指向新的地址为 现在的新节点指向原来的第一个节点，之后让原来指向第一个节点的 当然上述情况是在单链表本来就有节点的情况下，那样就可以直接在第一个节点之前插入，但是 当然上述情况是在单链表本来就有节点的情况下，那样就可以直接在第一个节点之前插入，但是如果一开始单链表为空的话，那就要添加判断条件让 们新们新new的节点，这样我们所 ，然后将原来的第一个节点的地址0x111放入刚刚的新节点中 现在指向新的地址为0x456的节点，这样就实现了头插法。 的节点，这样就实现了头插法。 的节点，这样我们所new的节点就直接为第一个节点。 的节点就直接为第一个节点。 ，里面的数据为5，然后将原来的第一个节点的地址 如果一开始单链表为空的话，那就要添加判断条件让head直接指向我 直接指向我 放入刚刚的新节点中(即即node.next=0x111)，这样就可以让 ，这样就可以让 public void addFirst(int data){ Node node = new Node(data); if(this.head == null){ //单链表中无节点 this.head = node; return; } node.setNext(this.head); this.head = node; } 3、尾插法 、尾插法 尾插法，首先首先 new一个新的节点， 尾插法， 新新new的节点地址放入到 的节点地址放入到cur之中，这样新的节点就成为新的尾节点。 之中，这样新的节点就成为新的尾节点。 一个新的节点，之后呢之后呢定义一个引用 定义一个引用cur，让，让cur指向指向head，开始一直遍历到最后直到 ，开始一直遍历到最后直到cur.next为空，这个时候 为空，这个时候cur指向的就是最后一个节点 指向的就是最后一个节点然后然后 将将
    public void addLast(int data){ Node node = new Node(data); if(this.head == null){ //单链表中无节点 this.head = node; return; } Node cur = this.head; while(cur.getNext()!=null){ cur = cur.getNext(); } //此时cur指向最后一个节点 cur.setNext(node); } 4、在任意位置插入 、在任意位置插入,第一个数据节点为 首先在插入的时候进行判断，判断index是否合法，之后如果 首先在插入的时候进行判断，判断 第一个数据节点为0号下标号下标 是否合法，之后如果index为为0，则直接进行头插，如果 ，则直接进行头插，如果 index等于单链表长度则直接进行尾插。 等于单链表长度则直接进行尾插。 设置一个方法得到prev，，prev指向指向index前一个节点的地址。 设置一个方法得到 前一个节点的地址。
    注意：这里一定要如图先将index的地址放入新节点中，之后再将新节点的地址放入原 注意：这里一定要如图先将 的地址放入新节点中，之后再将新节点的地址放入原index的前一个地址，如果顺序错误先进行 的前一个地址，如果顺序错误先进行3步骤则会丢失后面的数据。 步骤则会丢失后面的数据。 //在任意位置插入,第一个数据节点为0号下标 public Node findIndex(int index){//找到prev int count = 0; Node cur = this.head; while (count < index-1){ cur.setNext(cur.getNext()); count++; } return cur; } public void addIndex(int index,int data){ if(indexsize()){ throw new RuntimeException("输入位置不合法"); }else if(index == 0){ addFirst(data); }else if(index == size()){ addLast(data); }else { Node node = new Node(data); Node prev = findIndex(data); node.setNext(prev.getNext()); prev.setNext(node); } } public int size(){ int count = 0; Node cur = this.head; while (cur!=null){ count++; cur = cur.getNext(); } return count; } 、查找是否包含关键字key是否在单链表当中 5、查找是否包含关键字 是否在单链表当中
    //查找是否包含关键字key是否在单链表当中 public boolean contains(int key){ Node cur = this.head; while (cur!=null){ if(cur.getData() == key){ return true; } cur = cur.getNext(); } return false; } 6、删除第一次出现关键字为 、删除第一次出现关键字为key的节点的节点 删除关键字时首先要判断单链表之中是否存在这个关键字，其次判断这个关键字是否在第一个节点。之后按照常规的操作，先求出要删除的关键字的前驱 删除关键字时首先要判断单链表之中是否存在这个关键字，其次判断这个关键字是否在第一个节点。之后按照常规的操作，先求出要删除的关键字的前驱 如下图中如果要删除2关键字就要求得存储 的前驱的地址域就删除了2这个关键字节点。（这个地方存储 如下图中如果要删除 第一个节点） 第一个节点） 这个节点的后继地址放入2的前驱的地址域就删除了 这个关键字节点。（这个地方存储1的节点不是 的节点不是 关键字就要求得存储2这个节点的前驱，将 这个节点的前驱，将2这个节点的后继地址放入 //删除第一次出现关键字为key的节点 private Node findPrev(int key){ Node prev = this.head; while(prev.getNext()!=null){ if(prev.getNext().getData() == key){ return prev;
    } prev = prev.getNext(); } return null; } public void remove(int key){ if(this.head.getData() == key){ this.head = this.head.getNext(); return; } Node prev = findPrev(key); if(prev == null){ System.out.println("没有这个节点！"); return; } Node vel = prev.getNext(); prev.setNext(vel.getNext()); } 7、删除所有值为 、删除所有值为key的节点的节点 一次性删除所有关键字key，首先定义两个引用 一次性删除所有关键字 果果cur指向的节点的数值 指向的节点的数值=2，则将，则将cur向右移动即 域，域，prev.next=cur，之后将 节点。节点。 ，之后将prev移到移到cur位置，然后 ，首先定义两个引用prev和和cur，，cur为为prev的后继， 的后继，prev指向第一个节点 指向第一个节点，由下图举例，删除里面的所有的 ，由下图举例，删除里面的所有的2，定义好两个引用之后，如 ，定义好两个引用之后，如 向右移动即cur=cur.next，直到，直到cur指向节点的数值不为 指向节点的数值不为2，如下图此时将值为 ，如下图此时将值为4的节点地址放入 的节点地址放入prev的地址的地址 位置，然后cur继续进行判断直到 继续进行判断直到cur为空。当然如果第一个节点也需要删除的话只需添加判断条件之后将 为空。当然如果第一个节点也需要删除的话只需添加判断条件之后将head指向下一个 指向下一个 //删除所有值为key的节点 public void removeAllKey(int key){ Node prev = this.head; Node cur = prev.getNext(); while(cur!=null){ if(cur.getData() == key){ prev.setNext(cur.getNext()); }else{ prev = cur; } cur = cur.getNext();
    } if(this.head.getData() == key){ this.head = this.head.getNext(); } } 8、清空单链表 、清空单链表 单链表的清空很简单，因为在单链表上储存的是对象。所以会存在内存泄漏，所以在不引用之后要对内存进行回收。 单链表的清空很简单，因为在单链表上储存的是对象。所以会存在内存泄漏，所以在不引用之后要对内存进行回收。 所以清空单链表 所以清空单链表 第一种：只要将指向第一个节点的head置空，这样就没有被引用的节点。 第一种：只要将指向第一个节点的 置空，这样就没有被引用的节点。 第二种：就是一个一个进行释放。 第二种：就是一个一个进行释放。 先利用循环将第一个节点之后的所有节点删除，定义del指向指向head.next,之后将之后将dei.next放入放入head的的next域之中，不断循环直到 先利用循环将第一个节点之后的所有节点删除，定义 一个节点。 一个节点。 域之中，不断循环直到head的的next域为空此时再最后删除第 域为空此时再最后删除第 最后上代码！！！ 最后上代码！！！ class Node{ private int data; private Node next; //利用引用类型储存地址，因为已经定义Node所以可以直接引用 public Node(int data){ this.data = data; this.next = null; } public Node getNext() { return next; } public void setNext(Node next) { this.next = next; } public int getData() { return data; } public void setData(int data) { this.data = data; } } //组成单链表 public class MyLineList { public Node head; //定义一个头节点 public MyLineList(){ this.head = null; //设置头节点为空，也可以不设置 } //打印单链表
    分享到：
    赞 收藏

    相关推荐

    资料库

    开发技术

    共收录19306份资料，累计14个分类，关注成员有19位，主要包括：Actionscript,Javascript,PHP,VB,Perl,Delphi,Python,C#,C,Java,C++,Web开发,硬件开发,其它

    热门标签

    Actionscript Javascript PHP VB Perl Delphi Python C# C Java C++ Web开发 硬件开发 其它

    最新资料