网页设计建设网站模板,网上最好的网站模块,怎样做pdf电子书下载网站,网站开发为什么需要域名目录 一、链表
二、代码实现
1.创建结点
2.构造函数
3.链表的相关属性
4.添加虚拟节点
5.判断链表是否为空
6.添加方法
#xff08;1#xff09;在头部添加
#xff08;2#xff09;在尾部添加
#xff08;3#xff09;在索引位置添加
#xff08;4#xff…目录 一、链表
二、代码实现
1.创建结点
2.构造函数
3.链表的相关属性
4.添加虚拟节点
5.判断链表是否为空
6.添加方法
1在头部添加
2在尾部添加
3在索引位置添加
4对头插法和尾插法代码进行简化调用任意位置添加的方法
7.打印链表遍历重写toString方法
8.获取链表元素个数链表长度
9.获取链表结点
1获取头结点
2获取尾结点
3获取指定位置结点
10.判断结点是否存在
11.删除结点
1删除头结点
2删除尾节点
3在指定位置删除结点
4删除元素
5不使用虚拟节点删除 一、链表
链表是真正的动态数据结构也是最简单的动态数据结构。
动态数据结构还有二叉树trie等
优点不需要处理固定容量的问题真正的动态
缺点丧失了随机访问的能力
学习链表有助于更深理解引用和递归
二、代码实现
1.创建结点
使用内部类来创建结点
//使用内部类——创建结点class NodeT{T data;//节点本身Node next;//指向下个节点
2.构造函数
两个构造函数传入的参数不同
public Node(T data){this.datadata;this.nextnull;}public Node(T data,Node next){this.datadata;this.nextnull;}}
3.链表的相关属性
头结点和结点个数链表长度
private Node head;//头结点private int size;//表示链表中有多少个结点
4.添加虚拟节点
public SelfLinkedList(){//创建一个虚拟头结点Node dummyHeadnew Node(Integer.MIN_VALUE);this.headdummyHead;this.size0;dummyHead.nexthead;}
5.判断链表是否为空
public boolean isEmpty(){return this.size0;}
6.添加方法
1在头部添加
public void addHead(T data){//创建一个节点Node node new Node(data);//挂接node.nextthis.head;this.headnode;//更新sizethis.size;}
2在尾部添加
public void addTail(T data){Node nodenew Node(data);//针对空链表做处理if(this.headnull){this.headnode;this.size;return;}Node curNodethis.head;while(curNode.next!null){curNodecurNode.next;}curNode.nextnode;this.size;}
3在索引位置添加
//在任意位置添加public void add(int index,T data){//判断index是否有效if(index0||indexthis.size){throw new IllegalArgumentException(index is invalid);}//创建一个节点Node node new Node(data);//特殊处理1如果索引为0,if(index0){this.headnew Node(data,this.head);this.size;return;}//特殊处理2链表为空异常已抛出//找前驱结点从头开始找让索引移动index-1次Node prethis.head;for(int i1;iindex;i){prepre.next;}//开始进行结点的挂接node.nextpre.next;pre.nextnode;this.size;}
4对头插法和尾插法代码进行简化调用任意位置添加的方法
//在头部添加public void addHead(T data){add(0,data);}//在尾部添加public void addTail(T data){add(this.size,data);}
7.打印链表遍历重写toString方法
//打印整个链表Overridepublic String toString() {//从this。head开始一直向后Node curNodethis.head.next;StringBuilder sbnew StringBuilder();while(curNode!null){sb.append(curNode.data--);curNodecurNode.next;}sb.append(null);return sb.toString();}
8.获取链表元素个数链表长度 //获取链表中元素的个数public int getSize(){return this.size;}
9.获取链表结点
1获取头结点
//获取链表的头结点public Optional getFirst(){if(this.head.nextnull){return Optional.empty();}return Optional.ofNullable(this.head.next.data);}
2获取尾结点
//获取链表的尾结点public Optional getLast(){if(this.head.nextnull){return Optional.empty();}NodeT curNodethis.head;while(curNode.next!null){curNodecurNode.next;}return Optional.of(curNode.data);}
3获取指定位置结点 //从链表中获取任意位置的结点public T get(int index) {if (index 0 || index this.size) {throw new IllegalArgumentException(index is invalid);}NodeT curNode this.head.next;int i 0;while (i index) {curNode curNode.next;i;}return curNode.data;}
10.判断结点是否存在 //从链表中查找指定位置元素是否存在public boolean contains(T data) {Node curNode this.head.next;while (curNode ! null) {if (curNode.data.equals(data)) {return true;}}return false;}
11.删除结点
1删除头结点 //从链表的头部删除元素public T removeHead() {if (this.isEmpty()) {return null;}NodeT delNode this.head.next;this.head.next delNode.next;delNode.next null;//更新size;this.size--;return delNode.data;}
2删除尾节点
//链表的尾部删除元素public T removeTail() {if (this.isEmpty()) {return null;}NodeT pre this.head;while (pre.next.next ! null) {pre pre.next;}NodeT delNode pre.next;pre.next delNode.next;delNode.next null;//更新size;this.size--;return delNode.data;}
3在指定位置删除结点
//删除任意位置的结点public T remove(int index){if(index0||indexthis.size){throw new IllegalArgumentException(index is invalid);}//找删除结点的前驱NodeTprethis.head;int i0;while(iindex){prepre.next;i;}NodeTdelNodepre.next;pre.nextdelNode.next;delNode.nextnull;this.size--;return delNode.data;}
4删除元素
//根据值从链表中删除元素public int removeByValue(T value){int count0;//定义前驱结点NodeTprethis.head;while(pre.next!null){Node curNodepre.next;if(curNode.data.equals(value)){pre.nextpre.next.next;curNode.nextnull;this.size--;count;}else{prepre.next;}}return count;}
5不使用虚拟节点删除
//不使用虚拟头结点public int removeByValue2(T val){int count 0;NodeT realHead this .head.next;while(realHead!nullrealHead.data.equals(val)){realHeadrealHead.next;this.size--;count;}//判断链表是否为空if(realHeadnull){return count;}//头结点不是删除的点Node pre realHead;while(pre.next!null){NodeT delNode pre.next;if(delNode.equals(val)){pre.next delNode .next;delNode.next null;this.size--;count;}else{pre pre .next;}}return count;}三、完整代码
package com.algo.lesson.lesson03;import java.util.Optional;
import java.util.Random;public class SelfLinkedListT {//使用内部类——创建结点class NodeT {T data;//节点本身Node next;//指向下个节点public Node(T data) {this.data data;this.next null;}public Node(T data, Node next) {this.data data;this.next null;}}//链表相关的属性和方法private Node head;//头结点private int size;//表示链表中有多少个结点public SelfLinkedList() {//创建一个虚拟头结点Node dummyHead new Node(Integer.MIN_VALUE);this.head dummyHead;this.size 0;dummyHead.next head;}//判断链表是否为空public boolean isEmpty() {return this.size 0;}//向链表中添加结点//在头部添加public void addHead(T data) {/*//创建一个节点Node node new Node(data);//挂接node.nextthis.head;this.headnode;//更新sizethis.size;*/add(0, data);}//在尾部添加public void addTail(T data) {/*Node nodenew Node(data);//针对空链表做处理if(this.headnull){this.headnode;this.size;return;}Node curNodethis.head;while(curNode.next!null){curNodecurNode.next;}curNode.nextnode;this.size;*/add(this.size, data);}//在任意位置添加public void add(int index, T data) {//判断index是否有效if (index 0 || index this.size) {throw new IllegalArgumentException(index is invalid);}//创建一个节点Node node new Node(data);//特殊处理1如果索引为0,if (index 0) {this.head new Node(data, this.head);this.size;return;}//特殊处理2链表为空异常已抛出//找前驱结点从头开始找让索引移动index-1次Node pre this.head;for (int i 1; i index; i) {pre pre.next;}//开始进行结点的挂接node.next pre.next;pre.next node;this.size;}//打印整个链表Overridepublic String toString() {//从this。head开始一直向后Node curNode this.head.next;StringBuilder sb new StringBuilder();while (curNode ! null) {sb.append(curNode.data --);curNode curNode.next;}sb.append(null);return sb.toString();}//从链表中查找指定位置元素是否存在public boolean contains(T data) {Node curNode this.head.next;while (curNode ! null) {if (curNode.data.equals(data)) {return true;}}return false;}//获取链表中元素的个数public int getSize() {return this.size;}//获取链表的头结点public Optional getFirst() {if (this.head.next null) {return Optional.empty();}return Optional.ofNullable(this.head.next.data);}//获取链表的尾结点public Optional getLast() {if (this.head.next null) {return Optional.empty();}NodeT curNode this.head;while (curNode.next ! null) {curNode curNode.next;}return Optional.of(curNode.data);}//从链表中获取任意位置的结点public T get(int index) {if (index 0 || index this.size) {throw new IllegalArgumentException(index is invalid);}NodeT curNode this.head.next;int i 0;while (i index) {curNode curNode.next;i;}return curNode.data;}//从链表的头部删除元素public T removeHead() {if (this.isEmpty()) {return null;}NodeT delNode this.head.next;this.head.next delNode.next;delNode.next null;//更新size;this.size--;return delNode.data;}//链表的尾部删除元素public T removeTail() {if (this.isEmpty()) {return null;}NodeT pre this.head;while (pre.next.next ! null) {pre pre.next;}NodeT delNode pre.next;pre.next delNode.next;delNode.next null;//更新size;this.size--;return delNode.data;}//删除任意位置的结点public T remove(int index){if(index0||indexthis.size){throw new IllegalArgumentException(index is invalid);}//找删除结点的前驱NodeTprethis.head;int i0;while(iindex){prepre.next;i;}NodeTdelNodepre.next;pre.nextdelNode.next;delNode.nextnull;this.size--;return delNode.data;}//根据值从链表中删除元素public int removeByValue(T value){int count0;//定义前驱结点NodeTprethis.head;while(pre.next!null){Node curNodepre.next;if(curNode.data.equals(value)){pre.nextpre.next.next;curNode.nextnull;this.size--;count;}else{prepre.next;}}return count;}//不使用虚拟头结点public int removeByValue2(T val){int count 0;NodeT realHead this .head.next;while(realHead!nullrealHead.data.equals(val)){realHeadrealHead.next;this.size--;count;}//判断链表是否为空if(realHeadnull){return count;}//头结点不是删除的点Node pre realHead;while(pre.next!null){NodeT delNode pre.next;if(delNode.equals(val)){pre.next delNode .next;delNode.next null;this.size--;count;}else{pre pre .next;}}return count;}
