使用头和尾引用的单链列表删除元素

samz_manu

我必须为我的项目实现一个单链列表,但我无法使remove方法起作用。我在这里搜索了答案,但是找不到包含尾部引用的任何答案。我的项目需要在列表中有头和尾参考,并且需要在需要时进行更新。这是我的课程和remove方法:

public class BasicLinkedList<T> implements Iterable<T> {
public int size;

protected class Node {
    protected T data;
    protected Node next;

    protected Node(T data) {
        this.data = data;
        next = null;
    }
}

protected Node head;
protected Node tail;

public BasicLinkedList() {
    head = tail = null;
}

public BasicLinkedList<T> addToEnd(T data) {
    Node n = new Node(data);
    Node curr = head;
    //Check to see if the list is empty
    if (head == null) {
        head = n;
        tail = head;
    } else {
        while (curr.next != null) {
            curr = curr.next;
        }
        curr.next = n;
        tail = n;

    }
    size++;
    return this;
}

public BasicLinkedList<T> addToFront(T data) {
    Node n = new Node(data);
    if(head == null){
        head = n;
        tail = n;
    }
    n.next = head;
    head = n;
    size++;
    return this;
}

public T getFirst() {
    if (head == null) {
        return null;
    }
    return head.data;
}

public T getLast() {
    if(tail == null){
        return null;
    }
    return tail.data;
}

public int getSize() {
    return size;
}

public T retrieveFirstElement() {
    // Check to see if the list is empty
    if (head == null) {
        return null;
    }
    Node firstElement = head;
    Node curr = head.next;
    head = curr;
    size--;
    return firstElement.data;

}

public T retrieveLastElement() {
    Node curr = head;
    Node prev = head;
    // Check to see if the list is empty
    if (head == null) {
        return null;
    } else {
        // If there's only one element in the list
        if (head.next == null) {
            curr = head;
            head = null;
        } else {
            while (curr.next != null) {
                prev = curr;
                curr = curr.next;
            }

            tail = prev;
            tail.next = null;
        }
    }
    size--;
    return curr.data;
}

public void remove(T targetData, Comparator<T> comparator) {
    Node prev = null, curr = head;
    while (curr != null) {
        if (comparator.compare(curr.data, targetData) == 0) {
            //Check to see if we need to remove the very first element
            if (curr == head) {
                head = head.next;
                curr = head;
            } 
            //Check to see if we need to remove the last element, in which case update the tail
            else if(curr == tail){
                curr = null;
                tail = prev;
                prev.next = null;
            }
            //If anywhere else in the list
            else {
                prev.next = curr.next;
                curr = curr.next;
            }
            size--;
        } else {
            prev = curr;
            curr = curr.next;
        }
    }
}

public Iterator<T> iterator() {
    return new Iterator<T>() {

        Node current = head;

        @Override
        public boolean hasNext() {
            return current != null;
        }

        @Override
        public T next() {
            if(hasNext()){
                T data = current.data;
                current = current.next;
                return data;
            }
            return null;
        }

        @Override
        public void remove(){
            throw new UnsupportedOperationException("Remove not implemented.");
        }

    };
}

}

我已经经历了这种方法的许多迭代,每次我丢失头参考,尾参考或者我不删除该元素时,都会为解决这个问题而烦恼。作为参考,这里是我正在运行的测试。我什至没有通过测试,只是说失败跟踪。

public void testRemove(){
            BasicLinkedList<String> basicList = new BasicLinkedList<String>();
    basicList.addToEnd("Blue");
    basicList.addToEnd("Red");
    basicList.addToEnd("Magenta");
    //Blue -> Red -> Magenta -> null
    basicList.remove("Red", String.CASE_INSENSITIVE_ORDER);
    //Blue -> Magenta -> null
    assertTrue(basicList.getFirst().equals("Blue"));
    //getLast() returns the tail node
    assertTrue(basicList.getLast().equals("Magenta"));
    }

编辑:忘记提及remove方法应该从列表中删除目标数据的所有实例。

奥利弗·戴恩(Oliver Dain)

我只看到1个错误。如果您的列表最初是空的,则以下方法将导致一个循环,在该循环中您有一个节点,下一个节点指向自身:

public BasicLinkedList<T> addToFront(T data) {
    Node n = new Node(data);
    // The list was empty so this if is true
    if(head == null){
        head = n;
        tail = n;
    }
    n.next = head;
    // now head == n and n.next == head == n so you've got a circle
    head = n;
    size++;
    return this;
}

您可以这样解决:

public BasicLinkedList<T> addToFront(T data) {
    Node n = new Node(data);
    if(head == null){
        tail = n;
    }
    n.next = head;
    head = n;
    size++;
    return this;
}

本文收集自互联网,转载请注明来源。

如有侵权,请联系 [email protected] 删除。

编辑于
0

我来说两句

0 条评论
登录 后参与评论

相关文章