什么是 Java 中的 LinkedListNode [英] What is LinkedListNode in Java
问题描述
请原谅我的无知，但我正在开始准备我的第一次技术面试，并在主题链表上遇到了这个问题和答案
问题:实现一个算法来删除单个链表中间的节点，只允许访问该节点
<前>公共静态布尔删除节点(LinkedListNode n){if (n == null || n.next == null) {返回假；//失败}LinkedListNode next = n.next;n.data = next.data;n.next = next.next;返回真；}我想开始使用此代码(进行更改编译测试)，但我不确定如何开始在 Java 中执行此操作.我在 Java 文档中找不到 LinkedListNode 类.
这可能是一个非常愚蠢的问题，但如果有人能指出我正确的方向 - 会很感激的.
编辑
感谢您快速而有用的回复.我想我的问题不是很清楚.上面的算法是作为该问题的解决方案提供的.我想知道如何在 Java 中实现它，以便我可以使用代码.
谢谢
只有当列表中有尾节点时，代码才能正常工作.
该算法使用以下逻辑
引用要删除的节点时，称其为curr"当引用curr"之前的节点时，称其为prev"当引用curr"之后的节点时，称其为next"为了有效地删除我们的节点，prev".next 应该指向next"它目前指向curr"我们的问题是我们没有提到prev"我们知道prev".next指向curr"由于我们无法改变prev".next 指向curr"的事实，我们必须让curr"狼吞虎咽next"我们让curr"的数据成为next"的数据我们让 "curr"s next 成为 "next"s next这仅在有尾翼时才有效的原因这样我们就可以让next"成为列表.(它的数据为空，其次为空.)否则，"prev".next 仍然会指向某些东西.这是一个使用 LinkedListNode 的类.我应该注意，如果你申请程序员职位，你应该能够基本上凭记忆做到这一点.:-)
class LinkedList{静态类 LinkedListNode{E数据；LinkedListNode下一个;}/*** 不完全是最好的面向对象，但我们会管理*/静态<E>E deleteNode(LinkedListNode节点){if(node == null || node.next == null) return null;E retval = node.data;LinkedListNode下一个 = node.next;node.data = next.data;node.next = next.next;返回 retval;}私有 LinkedListNode头;私有 LinkedListNode尾巴;公共链表(){this.head = new LinkedListNode();this.tail = new LinkedListNode();head.next = 尾；}公共无效 addLast(E e) {LinkedListNodenode = new LinkedListNode();//e 和 next 为空尾部数据 = e;tail.next = 节点；尾=节点；}公共无效 addFirst(E e) {LinkedListNodenode = new LinkedListNode();//e 和 next 为空；node.next = head.next;node.data = e;head.next = 节点；}公共 E 删除第一(){LinkedListNode第一个 = 头.下一个；head.next = first.next;返回 first.data;}公共 E deleteLast() {//不能没有列表的迭代！:-(抛出新的 UnsupportedOperationException();}公共 LinkedListNodefindFirst(E e) {LinkedListNodecurr = head.next;while(curr != null) {if(curr.data != null && curr.data.equals(e)) return curr;curr = curr.next;}返回空；}公共无效打印(){LinkedListNodecurr = head.next;while(curr.next != null) {System.out.println(curr.data);curr = curr.next;}}公共静态无效主(字符串 [] args){LinkedListlist = new LinkedList();list.addLast("苹果");list.addLast("熊");list.addLast("椅子");list.addLast("污垢");//list.print();LinkedListNode熊 = list.findFirst("熊");删除节点(熊)；列表打印()；}} Excuse my ignorance but I am beginning to prepare for my first technical interview and came across this question and answer on the topic linkedlist
Question: Implement an algorithm to delete a node in the middle of a single linked list, given only access to that node
public static boolean deleteNode(LinkedListNode n) {
if (n == null || n.next == null) {
return false; // Failure
}
LinkedListNode next = n.next;
n.data = next.data;
n.next = next.next;
return true;
}
I want to start playing with this code (making changes compile test) but I'm not sure how to start doing this in Java. I cannot find the LinkedListNode class in Java docs.
This might be a very silly question but if someone can point me in the right direction - will appreciate it.
EDIT
Thanks for the quick and useful responses. I guess my question was not very clear. The algorithm above was provided as a solution to that question. I wanted to know how to implement that in Java so I can play around with the code.
thanks
The code will only work properly if there's a tail node on the list.
The algorithm works with the following logic
When referring to the node to be deleted, call it "curr"
When referring to the node before "curr", call it "prev"
When referring to the node after "curr", call it "next"
To effectively delete our node, "prev".next should point to "next"
It currently points to "curr"
Our problem is that we have no reference to "prev"
We know "prev".next points to "curr"
Since we cannot change the fact that "prev".next points to "curr",
we must have "curr" gobble up "next"
We make "curr"s data be "next"s data
We make "curr"s next be "next"s next
The reason this only works if there's a tail guard
is so we can make "next" be the "tail" node of the
list. (Its data is null and it's next is null.) Otherwise,
"prev".next would still be pointing to something.
Here's a class that uses LinkedListNode. I should note that if you're applying for a position as a programmer, you should be able to do this basically from memory. :-)
class LinkedList<E> {
static class LinkedListNode<E> {
E data;
LinkedListNode<E> next;
}
/**
* Not exactly the best object orientation, but we'll manage
*/
static <E> E deleteNode(LinkedListNode<E> node) {
if(node == null || node.next == null) return null;
E retval = node.data;
LinkedListNode<E> next = node.next;
node.data = next.data;
node.next = next.next;
return retval;
}
private LinkedListNode<E> head;
private LinkedListNode<E> tail;
public LinkedList() {
this.head = new LinkedListNode<E>();
this.tail = new LinkedListNode<E>();
head.next = tail;
}
public void addLast(E e) {
LinkedListNode<E> node = new LinkedListNode<E>(); // e and next are null
tail.data = e;
tail.next = node;
tail = node;
}
public void addFirst(E e) {
LinkedListNode<E> node = new LinkedListNode<E>(); // e and next are null;
node.next = head.next;
node.data = e;
head.next = node;
}
public E deleteFirst() {
LinkedListNode<E> first = head.next;
head.next = first.next;
return first.data;
}
public E deleteLast() {
// cannot do without iteration of the list! :-(
throw new UnsupportedOperationException();
}
public LinkedListNode<E> findFirst(E e) {
LinkedListNode<E> curr = head.next;
while(curr != null) {
if(curr.data != null && curr.data.equals(e)) return curr;
curr = curr.next;
}
return null;
}
public void print() {
LinkedListNode<E> curr = head.next;
while(curr.next != null) {
System.out.println(curr.data);
curr = curr.next;
}
}
public static void main(String[] args) {
LinkedList<String> list = new LinkedList<String>();
list.addLast("Apple");
list.addLast("Bear");
list.addLast("Chair");
list.addLast("Dirt");
//list.print();
LinkedListNode<String> bear = list.findFirst("Bear");
deleteNode(bear);
list.print();
}
}
这篇关于什么是 Java 中的 LinkedListNode的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
