如何获取链表的某个部分

Question

我在大学里有一个项目，我偶然发现了一个我无法解决的问题。

关于程序：我需要创建一个任务列表（它们可以是私人任务或业务任务）。我需要一个 return 仅包含私人任务列表的函数和另一个 return 仅包含业务任务列表的函数。所以我有一个 class "Task" 包含 "next" 和 "prev" 连接。 classes "PrivateTask" 和 "BusinessTask" 继承了这个 class。我还有一个 class ToDoList，我实际上在其中尝试创建列表。

class ToDoList
{

    Task first = null;
    Task last = null;

    //adds new tasks and sorts them right away
    public void AddSorted(Task newTask)
    {
        if(first == null)
        {
            first = newTask;
            last = newTask;
        }
        else
        {
            if(newTask < first)
            {
                Prepend(newTask);
            }
            else if(newTask > last)
            {
                Append(newTask);
            }
            else
            {
                Task loopTask = first;

                while(newTask > loopTask)
                {
                    loopTask = loopTask.next;
                }
                AddBefore(loopTask, newTask);
            }
        }

    }

    //adds a new task before another chosen task
    private void AddBefore(Task Next, Task newTask)
    {
        newTask.prev = Next.prev;
        newTask.next = Next;
        Next.prev.next = newTask;
        Next.prev = newTask;
    }

    //adds at the start of the list
    private void Prepend(Task newTask)
    {
        first.prev = newTask;
        newTask.next = first;
        first = newTask;
    }

    //adds at the end of the list
    private void Append(Task newTask)
    {
        last.next = newTask;
        newTask.prev = last;
        last = newTask;
    }

现在我需要 return BusinessTasks 列表

//returns a list of business tasks
public ToDoList GetBusinessList()
{
    ToDoList busList = new ToDoList();
    Task loopTask = first;

    while(loopTask != null)
    {
        if(loopTask is BusinessTask)
        {
            busList.AddSorted(loopTask);
        }
        loopTask = loopTask.next;
    }
    return busList;
}

但是当我return这个列表时，主列表的全部内容都与这个同步，我不明白为什么。

Answer 1

您没有将副本的任务放入新列表，而是将 参考文献 放入新列表。因此，您正在更改 相同的对象 。因此，当您将第一个列表中的项目推入第二个列表并因此 next and/or prev 发生更改时，您正在更改两个列表。

因此您需要复制原始列表中的项目并将新项目放入第二个列表中。

while(loopTask != null)
{
    if(loopTask is BusinessTask)
    {
        var clone = loopTask.Clone();
        busList.AddSorted(clone);
    }
    loopTask = loopTask.next;
}

现在显然你需要实现一个 Clone 方法来复制所有属性除了那些与列表中的位置相关的属性 (prev 和 next) 到 BusinessTask

的新实例

现在，如果您真的想让两个列表中的对象都成为对同一对象 的引用。所以改变一个属性会改变另一个，然后你可以通过从列表 node[=37= 中分离出 data 部分来变得聪明] 部分。所以你可以这样做：

public class TaskBase { public string SomeProperty { get; set; } } public class Node { public TaskBase Data { get; private set;} public Node Next { get; set; } public Node Prev { get; set; } public Node(TaskBase data) { Data = data; } public Node Clone() { // Now all the data part is the same object // so changing Data.SomeProperty in one list will be // reflected in both. But the Next and Prev properties // are independent. return new Node(Data); } }

然后您的循环可能如下所示：

while(loopTask != null) { if(loopTask.Data is BusinessTask) // assuming BusinessTask derives from BaseTask { var clone = loopTask.Clone(); // clone contains the same BusinessTask, but it's position in the new list // won't mess up the old list. busList.AddSorted(clone); } loopTask = loopTask.next; }

如何获取链表的某个部分

How to get a certain part of a linked list

c#

inheritance

doubly-linked-list