2

我想以相反的顺序将字符串插入双向链表。但我不确定如何以相反的顺序维护插入顺序。

这是我下面的代码。

theList.insertReverseLexicographicalOrder("B");
theList.insertReverseLexicographicalOrder("A");
theList.insertReverseLexicographicalOrder("H");
theList.insertReverseLexicographicalOrder("D");
theList.insertReverseLexicographicalOrder("E");

public void insertReverseLexicographicalOrder(String dd) {
    Link newLink = new Link(dd);
    if (isEmpty()){
        last = newLink;
    }           
        first.previous = newLink;
    }
    newLink.next = first;
    first = newLink;
}

基于我的解决方案的一些代码将不胜感激任何建议..

4

3 回答 3

1

好吧,您假设它已经以相反的顺序排列,因此您将需要某种循环,直到找到它应该去的地方..即

Z、Y、X、W、L、K、A

如果你要插入 M,那么你应该循环直到找到 L,它在字典上比 M 大,因此将它插入那里。因为节点有先前的指针,插入不应该太难自己弄清楚

于 2012-01-24T20:20:17.900 回答
0

您需要查看比较每个元素的列表。当您找到要插入的元素之后的元素时停止。我建议您在节点类中实现 compareTo 方法:http ://www.javapractices.com/topic/TopicAction.do?Id=10 并使用它进行比较

祝你好运。

于 2012-01-24T20:22:52.073 回答
0

如何将节点插入到链表中:

  1. 如果列表为空,新节点将成为第一个,如果我们跟踪它,也是最后一个
  2. 否则找到要插入的位置,有三种可能,
    a) 新节点必须在第一个节点之前插入
    b) 新节点必须在最后一个节点之后插入
    c) 新节点必须插入两个现有节点之间
  3. 更新适当的引用,可能是firstlast以及一些nextprevious字段,具体取决于它必须插入的位置
if (first == null) {
    // the list is empty so far
} else

要找到位置,首先将数据与第一个节点的数据进行比较,看看是否必须在第一个节点之前插入。

if (newLink.iData.compareTo(first.iData) > 0) {
    // put newLink before first
} else {

您必须将注意力集中在某个列表节点上。从头开始遵循列表,直到到达插入点:

    Link focus = first; // focus first node
    while(focus.next != null && newLink.iData.compareTo(focus.next.iData) < 0) {
        focus = focus.next;
    }
    // now you have to insert the new value behind focus, left as exercise
    if (focus.next == null) {
        // newLink becomes the last node in the list
    } else {
       // newLink has to be inserted between focus and focus.next
    }
}

然后插入。当心边缘情况,在前端和末端插入略有不同。

于 2012-01-24T20:19:02.847 回答