首页 > 其他分享 >9.19单链表带哨兵和双向链表带哨兵

9.19单链表带哨兵和双向链表带哨兵

时间：2023-09-19 21:57:38浏览次数：40  
标签：Node int value next 链表 哨兵 prev 表带 public

1.单链表

public class Main {
public static void main(String[] args) {
LNode L = new LNode();
L.addFirst(4);//头插
L.addFirst(3);
L.addFirst(2);
L.addFirst(1);
L.addLast(5);//尾插
L.Isempty();//判空
L.query();//遍历
System.out.println();
System.out.println(L.findLast().value);//最后一个结点
LNode.Node L2 = L.findNode(0);//指定索引查询
if (L2 == null) {
System.out.println("未查询到指定索引");
} else {
System.out.println(L2.value);
}
int i = L.valuecheck(1);
if (i == -1) {
System.out.println("不存在指定元素");
} else {
System.out.println("存在该元素，索引为" + i);
}
System.out.println("链表大小" + L.number());
L.removeIndex(0);
L.removeValue(2);
L.insertIndex(0, 2);
L.insertIndex(4, 6);
L.removeFirst();
L.removeLast();
L.query();

}

public static class LNode {
private Node head = new Node(-1, null);//头指针

public class Node {
int value;
Node next;

public Node(int value, Node next) {
this.value = value;
this.next = next;
}
}

//头插
public void addFirst(int value) {
head.next = new Node(value, head.next);
/* insertIndex(0,value);*/
}

//尾插
public void addLast(int value) {
Node node = findLast();
node.next = new Node(value, null);
}

//头删
public void removeFirst() {
removeIndex(0);
}

//尾删
public void removeLast() {
removeIndex(number() - 1);
}

//查找指定节点
public Node findNode(int index) {
int i = -1;
for (Node p = head; p != null; p = p.next) {
if (i == index) {
return p;
}
i++;
}
return null;
}

//找最后一个节点
public Node findLast() {
Node p;
for (p = head; p.next != null; p = p.next) {
}
return p;
}

//遍历
public void query() {
for (Node p = head.next; p != null; p = p.next) {
System.out.print(p.value + " ");
}
}

//返回链表实际元素长度不含头结点
public int number() {
int i = 0;
for (Node p = head.next; p != null; p = p.next) {
i++;
}
return i;
}

//查找指定值所在索引
public int valuecheck(int value1) {
int i = -1;
for (Node p = head.next; p != null; p = p.next) {
i++;
if (p.value == value1) {
return i;
}
}
return -1;
}

//删除指定索引节点
public void removeIndex(int index) {
Node prev = findNode(index - 1);
if (prev == null) {
System.out.println("空链表");
return;
}
Node removed = prev.next;
if (removed == null) {
System.out.println("索引不存在");
return;
}
prev.next = removed.next;
}

//删除指定值节点
public void removeValue(int value1) {
int i = -1;
int j = 0;
for (Node p = head.next; p != null; p = p.next) {
i++;
if (value1 == p.value) {
j++;
removeIndex(i);
}
}
if (j == 0) {
System.out.println("该值不存在");
}
}

//按索引插入指定值
public void insertIndex(int index, int value) {
Node prev = findNode(index - 1);
if (prev == null) {
System.out.println("插入失败");
return;
}
prev.next = new Node(value, prev.next);
}

//判空
public void Isempty() {
if (head.next == null) {
System.out.println("空链表");
} else {
System.out.println("非空链表");
}
}

}
}   2.双向链表
//优势操作最后节点方法简单，因为尾节点可知
public class Main {
public static void main(String[] args) {
DoubleLinkedList d=new DoubleLinkedList();
d.insertIndex(0,2);
d.addFirst(1);
d.addFirst(0);
d.addLast(3);
/* d.removeFirst();
d.removeIndex(0);
d.removeLast();
System.out.println(d.findNode(1).value);*/
d.query();

}

public static class DoubleLinkedList {
public static class Node {
Node prev;//上一个节点指针
int value;//值
Node next;//下一个节点指针

public Node(Node prev, int value, Node next) {
this.prev = prev;
this.value = value;
this.next = next;
}
public Node() {

}
}
private Node head;//头哨兵
private Node tail;//尾哨兵
public DoubleLinkedList()
{
head=new Node(null,-1,null);
tail=new Node(null,-1,null);
head.next=tail;
tail.prev=head;
}
public Node findNode(int index)
{
int i=-1;
for(Node p=head;p!=tail;p=p.next)
{
if(i==index)
{
return p;
}
i++;
}
return null;
}
public void insertIndex(int index,int value)
{
Node prev=findNode(index-1);
if(prev==null)
{
System.out.println("索引错误");
return ;
}
Node p=new Node(prev,value,prev.next);
prev.next.prev=p;
prev.next=p;
}
public void addFirst(int value)
{
insertIndex(0,value);
}
public void addLast(int value)
{
Node p=new Node(tail.prev,value,tail);
tail.prev.next=p;
tail.prev=p;
}
public void removeFirst()
{
Node remove=head.next;
remove.next.prev=head;
head.next=remove.next;
}
public void removeLast()
{
Node remove=tail.prev;
remove.prev.next=tail;
tail.prev=remove.prev;
}
public void removeIndex(int index)
{
Node prev=findNode(index-1);//被删除元素的前一个
if(prev==null)
{
System.out.println("删除失败");
return ;
}
Node remove=prev.next;//被删除元素
if(prev==tail)
{
System.out.println("删除失败");
return ;
}
Node Next=remove.next;//被删除元素的后一个
prev.next=Next;
Next.prev=prev;
}
public void query()
{
for(Node p=head.next;p!=tail;p=p.next)
{
System.out.print(p.value+" ");
}
}
}
}

标签：Node,int,value,next,链表,哨兵,prev,表带,public
From： https://www.cnblogs.com/zhaoqianwan/p/17715737.html

相关文章

  • 203.移除链表元素 707.设计链表 206.反转链表
    203.移除链表元素力扣题目链接(opensnewwindow)题意：删除链表中等于给定值val的所有节点。示例1：输入：head=[1,2,6,3,4,5,6],val=6输出：[1,2,3,4,5]示例2：输入：head=[],val=1输出：[]示例3：输入：head=[7,7,7,7],val=7输出：[]思路操作链表的两种方式：直接使用原来的......
  • 第二章 线性表-单链表
    线性表2.5.1单链表的定义和表示存储结构（物理位置）可以不连续。（非顺序映像/链式映像）typedefstructLNode{ ElemTypedata;//数据域 structLNode*next;//指针域}LNode,*LinkList;//（同一结构体指针类型起了两个名称）//LinkList是指向结构体LNode的指针类型//如......
  • 114. 二叉树展开为链表
    给你二叉树的根结点root，请你将它展开为一个单链表：展开后的单链表应该同样使用TreeNode，其中right子指针指向链表中下一个结点，而左子指针始终为null。展开后的单链表应该与二叉树先序遍历顺序相同。示例1：输入：root=[1,2,5,3,4,null,6]输出：[1,null,2,null,3,null,......
  • 如何在JavaScript中实现链表
      转载来自：https://www.freecodecamp.org/news/implementing-a-linked-list-in-javascript/  Ifyouarelearningdatastructures,alinkedlistisonedatastructureyoushouldknow.IfyoudonotreallyunderstanditorhowitisimplementedinJavaScript......
  • 删除链表的节点
    一、问题描述给定单向链表的头指针和一个要删除的节点的值，定义一个函数删除该节点。返回删除后的链表的头节点。1.此题对比原题有改动2.题目保证链表中节点的值互不相同3.该题只会输出返回的链表和结果做对比，所以若使用C或C++语言，你不需要free或delete被删除的节点# 二、......
  • 线性表之单链表（上）
    单链表就是一个表结构最后存储的位置是下一个表结构的地址，一般通过p->next表示存储的下一个位置的地址//link_list.htypedefintdata_t;typedefstructnode{data_tdata;structnode*next;}listnode,*linklist;linklistlist_create();intlist_tail_inser......
  • 剑指Offer面试题6：从尾到头打印链表
    一、题目输入一个链表的头节点，按链表从尾到头的顺序返回每个节点的值（用数组返回）如输入{1,2,3}的链表如下图:返回一个数组为[3,2,1]二、题解看到这题很多人第一反应是从头到尾输出会比较简单，于是我们很自然想到把链表中的节点指针反过来，改变链表结构就可以从头到尾输出了。但该方法......
  • 关于pta上6-2 两个有序链表序列的合并
    这是在dev上的源代码，C语言#include<stdio.h>#include<stdlib.h>typedefintElementType;typedefstructNode*PtrToNode;structNode{ElementTypeData;PtrToNodeNext;};typedefPtrToNodeList;ListRead();/*细节在此不表*/voidPrint(List......
  • 9.15单链表无哨兵java实现
    publicclassMain{publicstaticvoidmain(String[]args){LNodeL=newLNode();System.out.println(L.number());L.Isempty();L.addFirst(4);//头插L.addFirst(3);L.addFirst(2);L.addFirst(1);L.a......
  • [剑指offer] 链表篇
    JZ6从尾到头打印链表1/*从尾到头递归*/2publicclassJZ6_13{4privatestaticArrayList<Integer>res=newArrayList<>();56publicstaticArrayList<Integer>printListFromTailToHead(ListNodelistNode)7{8......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99