package linkedList.list;
import linkedList.node.ListNode;
public interface LinkedList<N extends ListNode<T>,T>
{
public boolean isEmpty();
public int size();
public String toString();
public T[] toArray(Class<? extends T> cl);
public LinkedList<N,T> fromArray(T[] array) throws ListAccessError;
}
package linkedList.list;
import linkedList.node.ListNode;
import java.lang.reflect.Array;
import java.util.ArrayList;
import java.util.Arrays;
public abstract class BasicList<N extends ListNode<T>,T> implements LinkedList<N,T> {
N root;
int size;
public boolean isEmpty() {
return size == 0;
}
public int size() {
return size;
}
public N getRoot() {
return root;
}
public void setRoot(N newRoot) {
root = newRoot;
}
public T[] toArray(Class<? extends T> cl) {
T[] array = (T[]) Array.newInstance(cl,size());
ListNode<T> node = getRoot();
for (int index = 0; index < size(); index++) {
array[index] = node.getValue();
node = node.getNext();
}
return array;
}
public String toString() {
if (isEmpty()) {
return "[]";
} else {
ListNode<T> currentNode = getRoot();
StringBuilder string = new StringBuilder("[" + currentNode.getValue());
while ((currentNode = currentNode.getNext()) != null) {
string.append("," + currentNode.getValue());
}
string.append("]");
return string.toString();
}
}
public String toString(int n) {
if (isEmpty()) {
return "[]";
} else {
ListNode<T> currentNode = getRoot();
StringBuilder string = new StringBuilder("[" + currentNode.getValue());
int added = 0;
while (added < n && (currentNode = currentNode.getNext()) != null) {
string.append("," + currentNode.getValue());
added++;
}
if (currentNode != null) {
string.append(",...");
}
string.append("]");
return string.toString();
}
}
}
package linkedList.list;
import com.sun.xml.internal.bind.v2.runtime.unmarshaller.XsiNilLoader;
import jdk.nashorn.internal.ir.IfNode;
import linkedList.node.ListNode;
import linkedList.node.SingleLinkNode;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
public class SingleLinkList<T> extends BasicList<SingleLinkNode<T>,T> implements List<T> {
public SingleLinkList<T> fromArray(T[] array) throws ListAccessError {
for (int index = array.length-1; index >= 0; index--) {
add(0,array[index]);
}
return this;
}
ListNode<T> getNode(int index) throws ListAccessError {
// Is the list empty? If so, cannot access the node.
if (isEmpty()) {
throw new ListAccessError("Cannot get node. List is empty.");
}
// Is the given index negative? If so, this is an error.
if (index < 0) {
throw new ListAccessError("Cannot get node. Negative index.");
}
ListNode<T> currentNode = getRoot(); // start at the root
while (index != 0 && currentNode != null) { // walk along the list (if haven't reached the end by hitting null node)
currentNode = currentNode.getNext(); // by getting next node in the list
index--; // and reducing index by one
}
// Reached the end of the list (by hitting null node)? If so, cannot access the required node.
if (currentNode == null) {
throw new ListAccessError("Cannot get node. Not enough nodes in the list.");
}
// Successfully found node by walking through until index was zero.
return currentNode;
}
public T get(int index) throws ListAccessError {
return getNode(index).getValue();
}
@Override
public void add(int index, T value) throws ListAccessError {
if (index > size() || index < 0) {
throw new ListAccessError("Index bigger than size.");
}
SingleLinkNode<T> newNode = new SingleLinkNode<T>(value);
SingleLinkNode<T> current = getRoot();
if(index==0) {
setRoot(newNode);
newNode.setNext(current);
size++;
} else {
while(--index > 0) {
current = current.getNext();
}
newNode.setNext(current.getNext());
current.setNext(newNode);
size++;
}
}
@Override
public T remove(int index) throws ListAccessError {
if (index >= size() || index < 0) {
throw new ListAccessError("Index out of bounds");
}
if (isEmpty()) {
throw new ListAccessError("List is empty cannot remove from list");
}
SingleLinkNode<T> current = getRoot();
SingleLinkNode<T> nextItem = getRoot().getNext();
return null;
}
}
package linkedList.node;
public class SingleLinkNode<T> implements ListNode<T>
{
private T value;
private SingleLinkNode<T> next;
public SingleLinkNode(T value) {
this.value = value;
next = null;
}
public SingleLinkNode(T value, SingleLinkNode<T> next) {
this.value = value;
this.next = next;
}
public T getValue() {
return value;
}
@Override
public void setValue(T value) {
this.value = value;
}
public SingleLinkNode<T> getNext() {
return next;
}
@Override
public void setNext(ListNode<T> node) {
next = (SingleLinkNode<T>) node;
}
public String toString() {
return value + (getNext() != null ? "=>" + getNext() : "");
}
}
我刚刚实现了 add 方法,该方法获取索引和值并将其插入到列表中的该位置。但是,当研究如何在索引处删除时,我无法找到任何仅使用给定索引删除节点的内容。欢迎任何帮助,并提前感谢任何解决方案!
当从链表中删除位于 I 位置的节点时,您需要做的就是
您只需删除指向 i 处所请求节点的“链接”,它就不再是链表的一部分。
首先,您必须检查这是否是您需要删除的第 0 个索引,因此您必须移动根。然后,要删除第 i 个根处的节点,您只需执行以下操作:
nodeBeforeI.setNext(nodeBeforeI.getNext().getNext());
完整代码:
public T remove(int index) throws ListAccessError {
if (index >= size() || index < 0) {
throw new ListAccessError("Index out of bounds");
}
if (isEmpty()) {
throw new ListAccessError("List is empty cannot remove from list");
}
SingleLinkNode<T> current = getRoot();
SingleLinkNode<T> removed;
if (index == 0){
removed = current;
setRoot(current.getNext()); // setting root to root.next
}else{
for (int i = 0; i < index -1; i++){
current = current.getNext();
}
removed = current.getNext();
current.setNext(current.getNext().getNext());
}
return removed.getValue();
}