addLast() Single Linked List Sentinel zen me xie?!

发布网友 发布时间：2024-10-24 07:24

我来回答

共4个回答

热心网友 时间：2024-10-25 14:13

public T addLast(T item){
int pointer = size;
Node node = sentinel;
while(pointer > 0) { //找到最后一个节点，因为是循环的，所以是私有属性sentinel的前面那个
node = node.next;
pointer--;
}
Node current = new Node(); //需要插入的节点
current.item = item;
current.next = sentinel;
node.next = current;
size++;
}
***********************************************************88
public T removeLast(){
if(size == 0) {System.out.println("你懂的");return;}
int pointer = size;
Node node = sentinel;
while(pointer > 1) { //找到last节点的前一个节点
node = node.next;
pointer--;
}
node.next = sentinel;
size--;
}
**********************************************************
public T delete(T item) {
if(size == 0) {System.out.println("你懂的");return;}
int pointer = size;
Node node = sentinel;
Node node1 = node; //记住node的前一个节点
while(pointer > 0) { //找到item相等的节点
node1 = node;
node = node.next;
if(node.item == item) {
System.out.println("你删掉我了");
node1.next = node.next; //调整list
size--;
return;
}
pointer--;
}
System.out.println("没找到");
return;
}
******************************************************************size用来记录你循环列表中有多少个节点，sentinel是不计数的，而且它永远为头结点和尾节点，你不要动它。你每次加入的时候都要new一个新的节点才能加入。注意size的变化

你每个函数返回值都是T，看看是否有必要

热心网友 时间：2024-10-25 14:14

fsefs

热心网友 时间：2024-10-25 14:16

package com.ht.CircularList;
public class SingleCircularListSentinel<T> {

private class Node { // When a new node is created, item and next are null

private T item = null;
private Node next = null;
}
private Node sentinel;
int size;

public SingleCircularListSentinel() {
sentinel = new Node();
sentinel.next = sentinel;
size = 0;
}

public T addLast(T item){
if(sentinel.next == sentinel && sentinel.item == null){
sentinel.item = item ;
}else{
//找到最末节点,循环链表中，首节点（标记节点）的前一个节点是末节点
Node node = findPreNode(sentinel);
Node lastNode = new Node();
lastNode.item = item ;
//将以前末节点的下一节点设为现在的末节点
node.next = lastNode ;
//将现在的末节点的next设为头节点
lastNode.next = sentinel;
}
size ++ ;
return item;
}

public T removeLast(){
//找到末节点
Node lastNode = findPreNode(sentinel);
if(lastNode == sentinel){
T item = sentinel.item ;
sentinel.item = null ;
return item ;
}
//找到末节点的前一节点
Node preLastNode = findPreNode(lastNode);
preLastNode.next = sentinel;
size -- ;
return lastNode.item;
}
public T delete(T item){
Node node = sentinel ;
//删除的是首节点
if(node.item == item){
if(size == 1){
sentinel.item = null;
size --;
}
if(size >= 2){
//找到末节点
Node lastNode = findPreNode(sentinel);
sentinel = sentinel.next;
lastNode.next = sentinel;
size --;
}
}
//删除非首节点
while((node = node.next) != sentinel){
if(node.item == item){
System.out.println("*******");
Node preNode = findPreNode(node);
preNode.next = node.next;
size --;
}
}
return item;
}
//找到目标节点的前一个节点
private Node findPreNode(Node targetNode) {
Node node = sentinel;
while((node = node.next) != targetNode){
if(node.next == targetNode){
return node ;
}
}
return sentinel ;
}
}

热心网友 时间：2024-10-25 14:14

what's mean ?