gpt4 book ai didi

java - 使用节点的双链表

转载 作者:行者123 更新时间:2023-11-30 10:47:07 25 4
gpt4 key购买 nike

我正在尝试创建一个添加函数,该函数将使用节点将新元素添加到链表,但由于某种原因它不起作用,我认为我做错了。

到目前为止,这是我的代码:

public void add(int pos, T e){

Node<T> active = this.head;
Node<T> pre = null;

int counter = 0;

while ((active != null) && (counter < pos)){
pre = active;
active = active.getRight();
counter = counter + 1;
}

if (counter == pos){

Node<T> mynode = new Node<T>(e);


if (pre == null){
this.head = mynode;
pre.setLeft(mynode);
}
else{
pre.setRight(mynode);
this.tail = mynode;
}


mynode.setRight(active);
mynode.setLeft(pre);
}


}

最佳答案

A) 在双向链表上添加方法

双向链表中,一个简单的添加方法如下;

// add method for single node
public void add(T value) {
if(head == null)
head = new Node<T>(value);
else {
Node<T> temp = head;
while(temp.next != null)
temp = temp.next;

tail = temp.next = new Node<T>(value);
tail.prev = temp;
}

size++;
}

但是,你想添加到列表中的特定位置;

B) 双向链表上的位置添加方法

// add method for specific position
// pos must be smaller/equal than the size of the list
public void addPos(int pos, T value) {
if(pos > size) // pos must be smaller/equal than size
return;

Node<T> newNode = new Node<>(value);
size++;

if(pos == 0) {
newNode.next = head;
head.prev = newNode;
head = newNode;

return;
} else if(pos == size-1) {
tail.next = newNode;
newNode.prev = tail;
tail = newNode;
} else {
Node<T> temp = head;
for(int i = 0; i < pos; i++)
temp = temp.next;

// insert newNode in the middle of temp.prev and temp
// temp.prev <-> newNode <-> temp

// attach newNode's prev and next references
newNode.next = temp;
newNode.prev = temp.prev;

// attach adjacent node's references to newNode
temp.prev.next = newNode;
temp.prev = newNode;
}
}

C) 双向链表类

public class DoublyLinkedList<T> {

protected Node<T> head;
protected Node<T> tail;
private int size;

public DoublyLinkedList() {
this.head = null;
this.tail = null;
this.size = 0;
}

// Overloaded add method for T[] list
public void add(T[] list) {
for(int i = 0; i < list.length; i++)
add(list[i]);
}

// add method for single node
public void add(T value) {
if(head == null)
head = new Node<T>(value);
else {
Node<T> temp = head;
while(temp.next != null)
temp = temp.next;

tail = temp.next = new Node<T>(value);
tail.prev = temp;
}

size++;
}

// add method for specific position
// pos must be smaller/equal than the size of the list
public void addPos(int pos, T value) {
if(pos > size) // pos must be smaller/equal than size
return;

Node<T> newNode = new Node<>(value);
size++;

if(pos == 0) {
newNode.next = head;
head.prev = newNode;
head = newNode;

return;
} else if(pos == size-1) {
tail.next = newNode;
newNode.prev = tail;
tail = newNode;
} else {
Node<T> temp = head;
for(int i = 0; i < pos; i++)
temp = temp.next;

// insert newNode in the middle of temp.prev and temp
// temp.prev <-> newNode <-> temp

// attach newNode's prev and next references
newNode.next = temp;
newNode.prev = temp.prev;

// attach adjacent node's references to newNode
temp.prev.next = newNode;
temp.prev = newNode;
}
}

public static class Node<T> {

protected T value;
protected Node<T> prev;
protected Node<T> next;

public Node(T value) {
this.value = value;
this.next = null;
this.prev = null;
}

@Override
public String toString() {
return value.toString();
}

}

public void printList() {
System.out.print("List : ");

if(head == null)
System.out.printf(" <empty>\n");
else {
Node<T> temp = head;

while(temp != null) {
System.out.print(temp + " ");
temp = temp.next;
}
}

System.out.println();
}

public void printReverse() {
System.out.print("List Reversed: ");

if(head == null)
System.out.printf(" <empty>\n");
else {
Node<T> temp = tail;

while(temp != null) {
System.out.print(temp + " ");
temp = temp.prev;
}
}

System.out.println();
}

public int getSize() {
return size;
}

}

D) 测试代码

public class TestDoublyLinkedList {

public static void main(String[] args) {
DoublyLinkedList<Integer> list = new DoublyLinkedList<>();

Integer[] intList = { 1, 3, 5, 7, 9 };
list.add(intList);

printState(list);

list.addPos(3, 88);

printState(list);
}

public static void printState(DoublyLinkedList<Integer> list) {
list.printList();
list.printReverse();
System.out.println("Head: " + list.head);
System.out.println("Tail: " + list.tail);
System.out.println("Size: " + list.getSize());
System.out.println("************************\n");
}
}

E) 输出

List         : 1 3 5 7 9 
List Reversed: 9 7 5 3 1
Head: 1
Tail: 9
Size: 5
************************

List : 1 3 5 88 7 9
List Reversed: 9 7 88 5 3 1
Head: 1
Tail: 9
Size: 6
************************

关于java - 使用节点的双链表,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/36251830/

25 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com