如何在双向链接列表的第一个节点之前插入新节点? [英] How do I insert a new node before first node of a doubly-linked list?
问题描述
我正在研究如何在双向链表的第一个节点之前插入一个新节点.我对执行此操作所需的辅助节点和执行该操作的步骤顺序感到困惑.我将很高兴提供有关如何解决此问题的提示，即我的 insertBeforeFirst 方法出了什么问题.就目前而言，该方法会导致nullPointerException，我发现很难解决.(注意:这是先前的后续内容>发布.)
I am looking at how to insert a new node before the first node of a doubly-linked list. I'm getting confused with the auxiliary nodes required for this operation and the sequence of steps in which to perform the operation. I would be grateful for a hint on how to solve this problem i.e. what is wrong with my insertBeforeFirst method. As it stands the method causes a nullPointerException which i find hard to troubleshoot. (note: this is a follow-on to a previous post.)
public DLL()
{
header = null ;
tail = null ;
}
...
DLL myList = new DLL() ;
DLLNode A = new DLLNode("Hello", null, null) ;
DLLNode B = new DLLNode("Hi", null, null) ;
...
myList.addFirst(A) ;
myList.insertBeforeFirst(B)
...
public void addFirst(DLLNode v)
{
v.pred = header ;
v.succ = tail ;
header = v ;
tail = v ;
}
...
public void insertBeforeFirst(DLLNode v)
{
DLLNode aux = v ;
aux.succ = header.succ ;
header = aux ;
DLLNode aux2 = aux.succ ;
aux2.pred = v ;
}
我遵循了Aaron的建议并进行了绘制，并且我有了一点改进，因为我不再得到nullPointerException了，但是新模式将插入第一个节点之后而不是之前.所以我想我的绘画技巧也需要一些磨合:)
I've followed Aaron's advice and made a drawing and i have a slight improvement in that i don't get a nullPointerException anymore but the new mode is inserted after the first node rather than before. So my drawing skills need some polishing too i think :)
public void insertBeforeFirst(DLLNode v)
{
v.succ = header.succ ; // point new node succ to current first node
header.succ = v ; //point header to new node
DLLNode aux = header.succ ; // auxiliary node for backward insertion
aux.pred = v ; // point auxiliary's pred backward to new node
}
看看MahlerFive的帖子，我现在明白为什么有些人可能对我的标题和尾巴说话感到困惑.这是我从这里得到的信息:为简化编程，在双向链接列表的两端添加特殊节点很方便:在列表标题之前的 header 节点列表尾部后面还有一个 trailer 节点.这些虚拟"节点不存储任何元素."
Looking at the post by MahlerFive I see now why some of you might get confused by my header and tail talk. Here is where i got it from: "To simplify programming, it is convenient to add special nodes at both ends of a doubly linked list: a header node just before the head of the list, and a trailer node just after the tail of the list. These "dummy" nodes do not store any elements" source
所以对于初学者来说，我需要找到一种方法来正确实现这些虚拟节点，然后再添加任何内容并做出正确的引用.这些DUMMY节点似乎需要不同的Node构造函数?可以通过DLL默认构造函数实例化它们吗?
So it seems that for a starter i need to find a way to implement these dummy nodes correctly before i can add anything and make correct references. these DUMMY nodes seem to require a different Node constructor? Could they be instantiated by the DLL default constructor?
@ MahlerFive，DLL构造函数将如下所示:
@MahlerFive, the DLL constructor will look like this:
public DLL()
{
DLLNode Header = new DLLNode(null, null, null) ;
DLLNode Tail = new DLLNode(null, Header, null) ;
Header.succ = Tail ;
}
和我的方法类似，尽管此刻我得到了nullPointerException:
and my method something like this, although i'm getting a nullPointerException at the moment:
// insert z before v
public void addBeforeFirst(DLLNode v, DLLNode z)
{
DLLNode aux = v.pred ;
z.pred = aux ;
z.succ = v ;
v.pred = z ;
aux.succ = z ;
}
我正在进步.(很棒的感觉！)我同意MahlerFive的观点，DUMMY Header和Tail节点不是解决此问题的好方法.但是，正如在已出版的有关该问题的书中提到的那样，至少值得探讨.这是我的新代码(不使用虚拟节点):
I'm making progress. (great feeling!) I am in agreement with MahlerFive that the DUMMY Header and Tail nodes are not a great way to approach this. But as it was mentioned in a published book on the matter it was worth at least exploring. Here goes my new code (without the use of dummy nodes):
...
// DLL Constructor
public DLL()
{
first = null ;
last = null ;
}
...
// example insert call
// B is the node in front of which i want to insert
l.insert("Ciao", B) ;
...
public void insert(String elem, DLLNode pred)
{
// make ins a link to a newly-created node with element elem,
// predecessor null, and successor null.
DLLNode ins = new DLLNode(elem, null, null) ;
// Insert ins at the insertion point in the
// forward SLL headed by first.
ins.pred = first ;
ins.succ = first ;
// let first be the the new node
first = ins ;
}
这需要微调，因为我还没有设置任何反向链接，但这是一个很好的起点.为了确保它正常工作(至少以向前的方式)，我添加了打印语句以在添加节点时打印出第一个和最后一个元素.实际上，它们已正确更新:
this needs fine tuning as i haven't set any backwards links yet but it's a great starting point. To make sure this works correctly (at least in the forward way) i added print statements to print out the first and last element as i added nodes. Indeed they were updated correctly:
Hi
first: hi
last: hi
Ciao Hi
first: Ciao
last: hi
Moin Ciao Hi
first: Moin
last: hi
推荐答案
您似乎最困惑的地方是 header 的工作方式.它只是对列表中第一个节点的引用.另外，也不需要辅助"节点.
It looks like most of your confusion is around how header works. It is just a reference to the first node in the list. Also, there is no need for an "auxiliary" node.
让我们看看您需要采取的步骤:
Lets look at the steps you need to take in order:
步骤1:设置要插入的节点的 pred .
Step 1: Set the pred of the node you are inserting.
由于该节点将成为第一个节点，因此它后面将没有任何节点，因此您可以说 v.pred = null;
Since the node will become the first node, it will have no nodes behind it, so you can say v.pred = null;
步骤2:设置要插入的节点的 succ .
Step 2: Set the succ of the node you are inserting.
我们的新节点需要指向旧的第一个节点.这就是混乱的所在.您可以执行以下操作:
Our new node needs to point forward to the old first node. Here's where the confusion comes. You do the following:
v.succ = header.succ;//将新节点succ指向当前的第一个节点
但是 header 是什么?它是对第一个节点的引用.说 header.succ 就是说您想要第一个节点后继，即第二个节点.当您看到 header 时，只需考虑第一个节点"，您将得出:
But what is header? It is a reference to the first node. By saying header.succ you are saying you want the first nodes successor, which is the second node. When you see header just think "first node" and you will come up with:
v.succ = header;
步骤3:将旧的第一个节点指向新节点
Step 3: Point the old first node back to the new node
您已经正确地执行了此步骤(请记住，认为标头是第一个节点"):
You already are doing this step correctly (remember, think header is "first node"):
header.succ = v;//将标头指向新节点
第4步:现在将新节点设置为标题
Step 4: Now make the new node the header
header = v;
编辑(针对您的#3编辑):最后，我将提出有关整个方法的一些问题，但是暂时不考虑这些问题，并假设您需要以这种方式设置列表...
EDIT (in response to your edit #3): There are some issues about this whole approach which I'll bring up at the end, but those aside for now and assuming you are required to set up your list this way...
假设您将列表的第一个节点(Header.succ)作为v传递，让我们执行相同的步骤:
Assuming you're passing in the first node of the list (Header.succ) as v, let's take the same steps:
步骤1:设置要插入的节点的 pred .
Step 1: Set the pred of the node you are inserting.
您希望新节点指向Header. v.pred =标头；
You want your new node to point back toward Header.
v.pred = Header;
步骤2:设置要插入的节点的 succ .
Step 2: Set the succ of the node you are inserting.
您希望新节点指向旧的第一个节点，即 Header.succ
You want your new node to point to the old first node, which was Header.succ
v.succ = Header.succ;
步骤3:将旧的第一个节点指向新节点
Step 3: Point the old first node back to the new node
确保您首先检查第一个节点(在我的第一篇文章中忘记了此信息)！
Make sure you check that a first node exists first (forgot this in my first post)!
if (Header.succ != null) {
Header.succ.pred = v; // Header.succ is the first node, and you want to set its pred reference
}
步骤4:现在将新节点设置为第一个节点
Step 4: Now make the new node the first node
Header.succ = v;
请注意，您甚至不需要 z ，因为您可以使用 Header.succ 到达第一个节点.这意味着您不需要它作为参数.
Note how you don't even need z since you can get to the first node using Header.succ. This means you shouldn't need it as a parameter.
现在，除了所有这些之外，您还应该考虑一些问题:
Now, all that aside there are some issues you should think about:
具有pred引用和数据字段的Header有什么意义?尾巴具有succ引用和数据字段的意义是什么?
What is the point of a Header having a pred reference and a data field? What is the point of a Tail having a succ reference and a data field?
如果您想使用此链接列表并插入项目，那么只需要为每个项目调用add()而不是addFirst()和addBeforeFirst()会更好吗?如果您可以使用remove()方法，那您将不得不跟踪列表是否为空或不知道要调用哪个方法addFirst()或addBeforeFirst()，这很丑陋.最好编写一个更通用的add()，以便要使用该列表的用户注意这一点.
If you wanted to use this linked list and insert items, wouldn't it be better if you just had to call add() for every item instead of addFirst() and addBeforeFirst()? What if you could a remove() method, then you'd have to keep track of if the list is empty or not to figure out which method to call, addFirst() or addBeforeFirst(), which is kind of ugly. It's better to write a more generalized add() which takes care of this for the user who is going to use the list.
这篇关于如何在双向链接列表的第一个节点之前插入新节点?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
