无头单向非循环链表的实现-创新互联
链表:是一种物理存储结构上非连续存储结构。
成都创新互联基于成都重庆香港及美国等地区分布式IDC机房数据中心构建的电信大带宽,联通大带宽,移动大带宽,多线BGP大带宽租用,是为众多客户提供专业服务器托管报价,主机托管价格性价比高,为金融证券行业成都机柜租用,ai人工智能服务器托管提供bgp线路100M独享,G口带宽及机柜租用的专业成都idc公司。无头单向非循环链表示意图:
下面就来实现这样一个无头单向非循环的链表。
1.头插法
public void addFirst(int elem) {
LinkedNode node = new LinkedNode(elem); //创建一个节点
if(this.head == null) { //空链表
this.head = node;
return;
}
node.next = head; //不是空链表,正常情况
this.head = node;
return;
}
2.尾插法
public void addLast(int elem) {
LinkedNode node = new LinkedNode(elem);
if(this.head == null) { //空链表
this.head = node;
return;
}
LinkedNode cur = this.head; //非空情况创建一个节点找到最后一个节点
while (cur != null){ //循环结束,cur指向最后一个节点
cur = cur.next;
}
cur.next = node; //将插入的元素放在最后节点的后一个
}
3.任意位置插入,第一个数据节点为0号下标
public void addIndex(int index,int elem) {
LinkedNode node = new LinkedNode(elem);
int len = size();
if(index < 0 || index > len) { //对合法性校验
return;
}
if(index == 0) { //头插
addFirst(elem);
return;
}
if(index == len) { //尾插
addLast(elem);
return;
}
LinkedNode prev = getIndexPos(index - 1); //找到要插入的地方
node.next = prev.next;
prev.next = node;
}
计算链表长度的方法:
public int size() {
int size = 0;
for(LinkedNode cur = this.head; cur != null; cur = cur.next) {
size++;
}
return size;
}
找到链表的某个位置的方法:
private LinkedNode getIndexPos(int index) {
LinkedNode cur = this.head;
for(int i = 0; i < index; i++){
cur = cur.next;
}
return cur;
}
4.查找关键字toFind是否包含在单链表当中
public boolean contains(int toFind) {
for(LinkedNode cur = this.head; cur != null; cur = cur.next) {
if(cur.data == toFind) {
return true;
}
}
return false;
}
5.删除第一次出现关键字为key的节点
public void remove(int key) {
if(head == null) {
return;
}
if(head.data == key) {
this.head = this.head.next;
return;
}
LinkedNode prev = seachPrev(key);
LinkedNode nodeKey = prev.next;
prev.next = nodeKey.next;
}
删除前应该先找到找到要删除元素的前一个元素:
private LinkedNode seachPrev(int key){
if(this.head == null){
return null;
}
LinkedNode prev = this.head;
while (prev.next != null){
if(prev.next.data == key){
return prev;
}
prev = prev.next;
}
return null;
}
6.删除所有值为key的节点
public void removeAllkey(int key){
if(head == null){
return;
}
LinkedNode prev = head;
LinkedNode cur = head.next;
while (cur != null){
if(cur.data == key){
prev.next = cur.next;
cur = prev.next;
} else {
prev = cur;
cur = cur.next;
}
}
if(this.head.data == key){
this.head = this.head.next;
}
return;
}
7.打印单链表
public void display(){
System.out.print("[");
for(LinkedNode node = this.head; node != null; node = node.next){
System.out.print(node.data);
if(node.next != null){
System.out.print(",");
}
}
System.out.println("]");
}
8.清空单链表
public void clear(){
this.head = null;
}
另外有需要云服务器可以了解下创新互联scvps.cn,海内外云服务器15元起步,三天无理由+7*72小时售后在线,公司持有idc许可证,提供“云服务器、裸金属服务器、高防服务器、香港服务器、美国服务器、虚拟主机、免备案服务器”等云主机租用服务以及企业上云的综合解决方案,具有“安全稳定、简单易用、服务可用性高、性价比高”等特点与优势,专为企业上云打造定制,能够满足用户丰富、多元化的应用场景需求。
网站标题:无头单向非循环链表的实现-创新互联
URL地址:http://scyanting.com/article/dpecdh.html