#java #linked-list
#java #связанный список
Вопрос:
Я практикуюсь со списками ссылок и пытаюсь создать метод удаления с нуля, который удаляет узел в связанном списке, а также обновляет значения индекса, которые я связал с каждым узлом. Я пробовал некоторую логику для разных случаев, но они не кажутся правильными. Обновление индекса узла для каждого случая также не кажется правильным.
Переменные экземпляра класса LinkedList
public class LinkedList<E> implements DynamicList<E> {
LLNode<E> head;
LLNode<E> tail;
int llSize;
LinkedList(){
this.head = null;
this.tail = null;
this.llSize =0;
}
Класс узла
public class LLNode<E>{
E obj;
LLNode<E> previousPointer;
LLNode<E> nextPointer;
int index;
public LLNode(E obj){
this.obj = obj;
this.index=0;
}
public E getObj() {
return obj;
}
public LLNode<E> getPreviousPointer() {
return previousPointer;
}
public LLNode<E> getNextPointer() {
return nextPointer;
}
public int getIndex() {
return index;
}
public void setIndex(int index) {
this.index = index;
}
}
метод удаления
@Override
public E remove(E data) {
LLNode<E> nodeToRemove = new LLNode<>(data);
if(head == null){
return null;
}
if(head.getObj().equals(nodeToRemove.getObj())){
head = nodeToRemove.nextPointer;
//not sure if this works....
LLNode<E> currentNode = this.head;
for(int i=0; i < size()-2; i ){
currentNode.setIndex(i);
currentNode = currentNode.nextPointer;
}
return nodeToRemove.getObj();
}
//this is not right
if(nodeToRemove.nextPointer != null){
nodeToRemove.nextPointer.previousPointer = nodeToRemove.previousPointer;
// do I have to update the nodeToRemove's previous to point to its new next?
LLNode<E> currentNode = nodeToRemove;
int startIndex = size()- countFrom(nodeToRemove);
for(int i = 0; i < countFrom(nodeToRemove); i ){
currentNode.setIndex(startIndex);
startIndex ;
currentNode = currentNode.nextPointer;
}
return nodeToRemove.getObj();
}
if(nodeToRemove.previousPointer != null){
nodeToRemove.previousPointer.nextPointer = nodeToRemove.nextPointer;
//node index updating
LLNode<E> currentNode = nodeToRemove;
int startIndex = size()- countFrom(nodeToRemove);
for(int i = 0; i < countFrom(nodeToRemove); i ){
currentNode.setIndex(startIndex);
startIndex ;
currentNode = currentNode.nextPointer;
}
return nodeToRemove.getObj();
}
this.llSize--;
return null;
}
Метод countFrom
private int countFrom(LLNode<E> startNode){
int count=0;
while(startNode != null){
startNode = startNode.nextPointer;
count ;
}
return count;
}
Дайте мне знать, если потребуется больше кода.
Комментарии:
1. В случае собственного связанного списка Java: «Операции, которые индексируются в список, будут проходить по списку с начала или конца, в зависимости от того, что ближе к указанному индексу». Это означает, что сохраненных индексов нет, только размер списка. Это устраняет необходимость обхода списка для обновления сохраненных индексов каждый раз, когда элемент вставляется или удаляется.
2. Я бы предложил использовать элемент INIT вместо head и tail. Так что init=new LLNode(null) init.previousPointer = init.nextPointer = init; С помощью этого вы можете защитить множество нулевых проверок в операциях.
3. @rcgldr Спасибо за отзыв Я знал, что в LinkedList нет сохраненных индексов, но практическое упражнение, над которым я работаю, требует от меня закодировать метод ‘remove’ с параметром int . Это была самая большая путаница, с которой я столкнулся при его написании. Итак, единственный способ, которым я думал обратиться к узлам, — это прикрепить к ним индекс. Хотя связанные списки обычно не имеют индексов. Кроме этого, я не уверен, как бы я поступил по этому поводу.
4. @YHapticY — В чем было бы преимущество хранения индексов в узлах, поскольку это все равно потребовало бы обхода списка, чтобы найти соответствующий индекс?
5. @rcgldr Мне жаль, что я допустил ошибку. Метод ‘remove’ не требует параметра index. Но в классе есть другие методы, для которых требуется индекс int для параметра, то есть ‘subList (int start, int stop)’, ‘get (int index)’, поэтому я закодировал класс узла с параметром index, чтобы отслеживать индекс / позицию, которую узелнаходится в списке. Как я могу обращаться к позициям в LinkedList без привязки «индекса» элементов к узлам, а также использовать предоставленные сигнатуры методов ‘subList (int start, int stop)’, ‘get (int index)’?
Ответ №1:
Вам нужно только перенумеровать узлы, которые следуют за удаленным узлом.
Итак:
public E remove(E data) {
LLNode<E> nodeToRemove = new LLNode<>(data);
if(head == null){
return null;
}
// Adapt head and tail when necessary
if(tail.getObj().equals(nodeToRemove.getObj())){
tail = nodeToRemove.previousPointer;
}
if(head.getObj().equals(nodeToRemove.getObj())){
head = nodeToRemove.nextPointer;
}
// Rewire the list so it skips the node to remove
if(nodeToRemove.nextPointer != null){
nodeToRemove.nextPointer.previousPointer = nodeToRemove.previousPointer;
}
if(nodeToRemove.previousPointer != null){
nodeToRemove.previousPointer.nextPointer = nodeToRemove.nextPointer;
}
// Renumber the nodes that follow the removed node.
// (Those before it retain their index)
LLNode<E> currentNode = nodeToRemove.nextPointer;
int index = nodeToRemove.getIndex();
while (currentNode != null) {
currentNode.setIndex(index);
index ;
currentNode = currentNode.nextPointer;
}
this.llSize--;
return nodeToRemove.getObj();
}
Комментарии:
1. Спасибо, это намного проще.
Ответ №2:
Я понял это, и, похоже, теперь это работает хорошо, вот мои изменения.
метод get()
Добавлена переменная count для сравнения с переданным параметром, также мое сравнение while проверяло current.next, а не current и получало нулевой указатель.
public E get(int index) {
LLNode<E> current = this.head;
int count = 0;
while(current != null){
if(index == count) {
return current.getObj();
}
current = current.nextPointer;
count ;
}
return null;
}
метод remove()
Я использовал некоторое время вместо предыдущей логики. и немного упростил логику.
@Override
public E remove(E data) {
LLNode<E> current = this.head;
while(current != null){
if(current.getObj().equals(data)) {
LLNode<E> prev = current.previousPointer;
LLNode<E> next = current.nextPointer;
if(prev != null) {
prev.nextPointer = next;
}
if(next != null) {
next.previousPointer = prev;
}
llSize--;
return current.getObj();
}
current = current.nextPointer;
}
return null;
}