Java:双链接列表，它使用一个前哨节点作为零元素

Question

我必须实施一份双链名单，作为继续教育的一项工作。

有三个接口必须实现：

IValueElement

package schnittstellen; // schnittstellen == interfaces

public interface IValueElement
{
    public String getName();
    public void setName (String paramName);
    public int getValue() ;
    public void setValue(int paramValue);
}

IListElement

package schnittstellen; 

public interface IListElement
{
    public IValueElement getValueElement();
    public void setValueElement(IValueElement value);
    public IListElement getPredecessor();
    public void setPredecessor (IListElement predecessor);
    public IListElement getSuccessor();
    public void setSuccessor (IListElement successor);
}

IList

package schnittstellen; 

public interface IList
{
    public IListElement getHead ( ) ;
    public void insertAtTheEnd(IValueElement value);
    public void insertAtPos(int pos , IValueElement value);
    public IValueElement getElementAt(int position);
    public int getFirstPosOf(IValueElement value);
    public void deleteFirstOf(IValueElement value);
    public void deleteAllOf(IValueElement value);
    public boolean member (IValueElement value);
    public void reverse();
    public String toString();
}

实现IList的要求：

• 具有默认构造函数。
• 列表的头不允许变为空。
• 虚拟元素必须用作列表的第0元素。
• 头的前导引用必须指向列表的最后一个元素。

下面是接口的实现：

类IValueElement

package implementierung;

import schnittstellen.IValueElement;

public class ValueElement implements IValueElement
{
    private String name;
    private int value;

    public ValueElement(String name, int value) {
        if (name == null) {
            this.name = "";
        } else {
            this.name = name;
        }

        this.value = value;
    }

    public String getName() {
        return this.name;
    }

    public void setName(String paramName) {
        if (name == null) {
            this.name = "";
        } else {
            this.name = paramName;
        }
    }

    public int getValue() {
        return this.value;
    }

    public void setValue(int paramValue) {
        this.value = paramValue;
    }

    public String toString() {
        return "Name : " + this.name + ", "
                + "Value : " + this.value;
    }
}

类IListElement

package implementierung;

import schnittstellen.IListElement;
import schnittstellen.IValueElement;

public class ListElement implements IListElement
{
    private IValueElement valueElement;
    private IListElement predecessor;
    private IListElement successor;

    public ListElement(IValueElement value) {
        if (value == null) {
            value = new ValueElement("", 0);
        } 

        this.valueElement = value;

        this.predecessor = null;
        this.successor = null;
    }

    public IValueElement getValueElement() {
        return this.valueElement;

    }

    public void setValueElement(IValueElement value) {
        if (value == null) {
            value = new ValueElement("", 0);
        } else {
            this.valueElement = value;
        }

    }

    public IListElement getPredecessor() {
        return this.predecessor;
    }

    public void setPredecessor (IListElement predecessor) {     
        this.predecessor = predecessor;
    }

    public IListElement getSuccessor() {
        return this.successor;
    }

    public void setSuccessor(IListElement successor) {
        this.successor = successor;
    }
}

类列表

package implementierung;

import schnittstellen.IList;
import schnittstellen.IListElement;
import schnittstellen.IValueElement;

public class List implements IList
{
    private IListElement head;
    private IListElement end;
    private int length;

    public List() {
        this.head = new ListElement(new ValueElement("Dummy", 0));
        this.end = this.head;
        this.length = 1;
    }

    public IListElement getHead() {
        return this.head;
    }

    private ListElement createListElement(IValueElement value) {
        if (value == null) {
            return new ListElement(new ValueElement("", 0));
        } else {
            return new ListElement(value);
        }
    }

    public void insertAtTheEnd(IValueElement value) {         
        ListElement newElement = createListElement(value);
        IListElement currentEnd = this.end;

        currentEnd.setSuccessor(newElement);       
        newElement.setPredecessor(currentEnd);

        this.end = newElement;  
        this.length++;
    }

    @Override
    public void insertAtPos(int pos , IValueElement value) {
        ListElement newElement = createListElement(value);

        if (pos <= 1) {         
            newElement.setSuccessor(this.head.getSuccessor());
            newElement.setPredecessor(this.head);
            this.head.setSuccessor(newElement);
        } else if (pos > this.length) {
            newElement.setSuccessor(null);
            newElement.setPredecessor(this.end);
            this.end = newElement;
        } else {
            IListElement currentElement = this.head;

            for (int i = 1; i <= pos; i++) {
                currentElement = currentElement.getSuccessor();

                if (i == pos) {
                    IListElement predecessor = currentElement.getPredecessor(); 

                    newElement.setPredecessor(predecessor);
                    newElement.setSuccessor(currentElement);

                    predecessor.setSuccessor(newElement);
                    currentElement.setPredecessor(newElement);

                    break;
                }
            }
        }

        this.length++;
    }

    public IValueElement getElementAt(int position) {
        if (position <= 0 || position > this.length) {
            return null;
        } else if (position == 1) {
            return this.head.getSuccessor().getValueElement();
        } else {
            IListElement ret = this.head;

            for (int i = 1; i < position; i++) {
                ret = ret.getSuccessor();
            }

            return ret.getSuccessor().getValueElement();
        }
    }

    public int getFirstPosOf(IValueElement value) {
        IListElement currentElement = this.head;
        int i = 1;

        while ((currentElement = currentElement.getSuccessor()) != null) {   
            IValueElement currentValueElement =
                    currentElement.getValueElement();

            if (value == currentValueElement) {
                return i;
            }

            i++;
        }

        return -1;
    }

    public void deleteFirstOf(IValueElement value) {
        IListElement currentElement = this.head;

        while ((currentElement = currentElement.getSuccessor()) != null) {
            IValueElement currentValueElement =
                    currentElement.getValueElement();

            if (value == currentValueElement) {
                IListElement predecessor = currentElement.getPredecessor();
                IListElement successor = currentElement.getSuccessor();

                predecessor.setSuccessor(successor);
                // Successor? => Then it is NOT the last element in the list.
                if (successor != null) {
                    successor.setPredecessor(predecessor);
                } else {
                    this.end = predecessor; // In case it's the last element in the list it becomes the new end.
                }

                this.length--;

                return;
            }
        }
    }

    public void deleteAllOf( IValueElement value) {
        IListElement currentElement = this.head.getSuccessor();

        while (currentElement != null) {
            IValueElement currentValueElement =
                    currentElement.getValueElement();

            if (value == currentValueElement) {
                IListElement predecessor = currentElement.getPredecessor();
                IListElement successor = currentElement.getSuccessor();

                predecessor.setSuccessor(successor);

                if (successor != null) {
                    successor.setPredecessor(predecessor);
                } else {
                    this.end = predecessor;
                }

                currentElement = successor;

                this.length--;
            } else {
                currentElement = currentElement.getSuccessor();
            }    
        }
    }

    public boolean member (IValueElement value) {
        IListElement currentElement = this.head;

        while ((currentElement = currentElement.getSuccessor()) != null) {
            IValueElement currentValueElement =
                    currentElement.getValueElement();

            if (value == currentValueElement) {
                return true;
            }
        }

        return false;
    }

    public void reverse() {
        IListElement currentElement = this.head.getSuccessor();
        IListElement currentNext = currentElement;       
        IListElement currentFirst = currentElement;

        while (currentNext != null) {
            currentNext = currentElement.getSuccessor();

            if (this.getHead() == currentElement.getPredecessor()) {
                currentElement.setSuccessor(null);
                currentElement.setPredecessor(currentNext);
            } else if (currentNext != null) {
                currentElement.setSuccessor(currentElement.getPredecessor());
                currentElement.setPredecessor(currentNext);
            } else {
                currentElement.setSuccessor(currentElement.getPredecessor());
                currentElement.setPredecessor(this.head);
            }

            currentElement = currentNext;
        }

        this.head.setSuccessor(this.end);
        this.head.setPredecessor(currentFirst);
        this.end = currentFirst;
    }

    @Override
    public String toString() {
        IListElement currentElement = this.head;
        String ret = "Head: " + this.head.getValueElement().getName() + ", "
                + this.head.getValueElement().getValue() + "\n";

        while ((currentElement = currentElement.getSuccessor()) != null) {
            IValueElement currentValueElement =
                    currentElement.getValueElement();

            ret += currentValueElement.getName() + ", "
                    + currentValueElement.getValue() + "\n";
        }

        return ret + "End: " + this.end.getValueElement().getName() + ", " +
                this.end.getValueElement().getValue() + "\n";
    }
}

此外，我(自愿)参加了一堂考试课。因为我尝试了到目前为止所得到的。

package implementierung;

import schnittstellen.*;

public class ListTest
{
    public static void main (String[] args) {
        IList list = new List();
        IValueElement data01 = new ValueElement("K1", 10);
        IValueElement data02 = new ValueElement("K2", 20);
        IValueElement data03 = new ValueElement("K3", 30);
        IValueElement data04 = new ValueElement("K4", 40);
        IValueElement data05 = new ValueElement("K5", 50);

        list.insertAtTheEnd(data01);
        list.insertAtTheEnd(data02);
        list.insertAtTheEnd(data03);
        list.insertAtTheEnd(data04);
        list.insertAtTheEnd(data05);

        System.out.println(list.toString());

        // Testing reverse()
        list.reverse();
        System.out.println("After reverse --- \n" + list.toString());

        // Testing getHead()
        System.out.println(
                "Name of head element: "
                    + list.getHead().getValueElement().getName() + "\n");

        // Testing getElementAt()
        System.out.println("At 2: " + list.getElementAt(2).getName());
        System.out.println("At 3: " + list.getElementAt(3).getName());
        System.out.println("At 5: " + list.getElementAt(5).getName());

        // Testing insertAtPos()
        IValueElement atPosN = new ValueElement("A-B", 99);
        list.insertAtPos(3, atPosN);

        // Testing insertAtTheEnd()
        IValueElement atTheEnd = new ValueElement("X-Y-Z", 100);
        list.insertAtTheEnd(atTheEnd);

        // Testing getElementAt() after additional insert
        System.out.println("After additional insert : ");
        System.out.println("At 2: " + list.getElementAt(2).getName());
        System.out.println("At 3: " + list.getElementAt(3).getName());
        System.out.println("At 5: " + list.getElementAt(5).getName());

        // Testing getFirstPosOf
        System.out.println("Element found at : " + list.getFirstPosOf(data03));
        System.out.println("Element found at : " + list.getFirstPosOf(atPosN));
        IValueElement test1 = new ValueElement("D-E-F", 10);
        System.out.println("Element found at : "
                + list.getFirstPosOf(test1) + "\n");

        System.out.println(list.toString());
        // Testing member()
        IValueElement notMember = new ValueElement("x-y", 12);

        System.out.println(list.member(atPosN));
        System.out.println(list.member(notMember));
        System.out.println(list.member(data03));

        // Testing deleteFirstOf() 
        System.out.println("\nTrying to delete K3 - \n");
        list.deleteFirstOf(data03);
        System.out.println(list.toString());

        // Testing deleteAllOf() 
        System.out.println("\nTrying to delete all of K2 - \n");
        list.insertAtTheEnd(data02); // Add data02 a second time.
        System.out.println(list.toString());
        list.deleteAllOf(data02);
        System.out.println(list.toString());
    }
}

我应该指出，我试图根据我在相应的讲座中所理解的内容来实现一切。我避免上网。相反，我自己想出了一切，使自己对这些数据结构更加自信。

我似乎工作得很好。但我肯定是有缺陷的。甚至可能是错误。

因此，所有关于改进的提示、评论和建议都受到高度欢迎。

Answer 1

建议1: bug

您的反转操作将在空列表上进入一个无限循环。为了补救这一点，请写

public void reverse() {
    if (length == 1) {
        // Otherwise, on empty list infinite loop.
        return;
    }

    IListElement currentElement = this.head.getSuccessor();
    IListElement currentNext = currentElement;       
    IListElement currentFirst = currentElement;
    ...
}

建议2

而且，计算length中的前哨元素也很有趣。更好的设计就是忽略它，开始只计算实际的元素。此外，您所称的“元素”是实际的，称为列表节点。

建议3

在接口名称前加上I是一个C#约定，而不是一个C#约定。

建议4

您可以通过简单地交换元素/节点数据，而不是重构整个列表，从而使代码更加清晰：

public void reverseV2() {
    IListElement element1 = head.getSuccessor();
    IListElement element2 = end;

    while (head != end) {
        String tmpString = element1.getValueElement().getName();
        element1.getValueElement().setName(element2.getValueElement().getName());
        element2.getValueElement().setName(tmpString);

        int tmpInt = element1.getValueElement().getValue();
        element1.getValueElement().setValue(element2.getValueElement().getValue());
        element2.getValueElement().setValue(tmpInt);

        element1 = element1.getSuccessor();

        if (element1 == element2) {
            return;
        }

        element2 = element2.getPredecessor();

        if (element2 == element1) {
            return;
        }
    }
}

总的来说，您的代码非常清晰，而且编写得很好。