标签: doubly-linked-list

最近,我读过一篇文章,向我展示了如何使用单个指针字段实现双向链表,即像单个链表一样.与将XOR prev和下一个地址存储在单个字段中有关.我不知道这有助于我们前后横穿？谁可以给我解释一下这个？我在这里读过这篇文章.任何人都可以向我解释这个吗？更详细一点？XOR如何与这些地址有关.

什么时候使用双向链表似乎是现实生活场景中的最佳选择？有人可以建议实际使用吗？

我构建了一个std::list定期合并在一起的项目(图形组件结构).我的想法是,如果我发现一个连接两个组件的节点,它们就会成为一个组件,我的列表会枚举我的组件.每个组件都有一个句柄(在这种情况下是一个std::list<component>::iterator)到它的"父"组件,它在合并后设置.这种方式来确定特定节点所属的组件我走这个链.

最后,我正在寻找的是std::list允许我采用项目迭代器的操作N,并将其从列表中删除但不解除分配:列表其余部分的结构修改方式与完全相同.正常删除它.

最好不要重新分配项目,从列表中复制项目,以及调用真实项目remove或项目erase.

也许我可以用它完成它splice.我需要将要删除的元素拼接成"垃圾" list,不是吗？

我想知道使用append()构建Python v2.7列表的复杂程度是多少？Python列表是双重链接的,因此它是恒定的复杂性还是单独链接,因此是线性复杂性？如果它是单链接的,我怎样才能在线性时间内从迭代中建立一个列表,该列表按照从头到尾的顺序提供列表的值？

例如:

def holes_between(intervals):
  # Compute the holes between the intervals, for example:
  #     given the table: ([ 8,  9] [14, 18] [19, 20] [23, 32] [34, 49])
  #   compute the holes: ([10, 13] [21, 22] [33, 33])
  prec = intervals[0][1] + 1 # Bootstrap the iteration
  holes = []
  for low, high in intervals[1:]:
    if prec <= low - 1:
      holes.append((prec, low - 1))
    prec = high + 1
  return holes

我有一个三维结构......实际上是一个双向链表，有六个节点，即左、右、上、下、进、出。如果一个节点在另一个节点的右侧，那么该节点将明显位于第一个节点的左侧。喜欢

实际上这是一个 3D 结构，但为了便于理解，我给出了一个 2D 示例。现在我必须将其转换为 JSON 格式，以便通过 WCF 将此数据发送到客户端，但由于它包含循环，因此无法将其转换为 JSON。我有这些问题

1. 这种双向链表可以转成JSON吗？
2. 有没有另一种方法可以做到这一点？
3. 任何其他推荐的数据结构？如果使用双向链表这是不可能的。

我正在使用Json.Net来处理 JSON。

我的班级是

public class Node
{
    public Document document = null;

    public Node left = null;
    public Node right = null;
    public Node up = null;
    public Node down = null;
    public Node inside = null;
    public Node outside = null;
}

我需要使用双向链表数据结构，它允许我以恒定时间 ( O(1))在任何位置任意插入和/或删除元素，而无需重新索引任何内部数据结构。

我正在考虑实现我自己的数据结构，但后来我遇到了SplDoublyLinkedList（http://php.net/manual/en/class.spldoublylinkedlist.php）。

瞬间，有两件事让我怀疑：

1. 它的SplDoublyLinkedList::add ( mixed $index , mixed $newval )方法接受一个$index参数，据说它shuffles the previous value at that index (and all subsequent values) up through the list.
2. 它的 remove 对应方法SplDoublyLinkedList::offsetUnset也将索引作为参数，并重新索引双向链表的内部数组。

这两点让我觉得SplDoublyLinkedListin PHP 的行为更像是 Java ArrayList，其中数据结构的内部数组在每次插入/删除操作后都会一次又一次地重新索引。

事实上，如果你运行下面的代码，你会看到有一个内部数组被重新索引：

$dlist = new SplDoublyLinkedList();  
$dlist->push('A'); 
$dlist->push('B'); 
$dlist->push('C');

var_dump($dlist);

$dlist->add(1, 'Z');

echo "After insertion in the middle of the list:";

var_dump($dlist);

输出：

class SplDoublyLinkedList#1 (2) {
  private $flags => …

我一直在从事一个项目，我必须实现一个java类来实现双向链表的使用。我已经完成了 LinkedList 类的所有方法。我只是不确定如何实际将节点对象添加到列表中。这是到目前为止我的代码，测试在底部。任何帮助，将不胜感激。谢谢

public class LinkedList {

    private Node first;
    private Node current;
    private Node last;
    private int currentIndex;
    private int numElements;

    public LinkedList() {
        this.first = null;
        this.last = null;
        this.numElements = 0;
        this.current = null;
        this.currentIndex = -1;
    }

    private class Node {

        Node next;
        Node previous;
        Object data;
    }

    public boolean hasNext() {
        return (current != null && current.next != null);
    }

    public Object next() {
        if (!this.hasNext()) {
            throw new IllegalStateException("No next");
        }

        current = current.next; …

在我的Neo4J数据库中,我有一系列通过双链表实现的卡片队列.数据结构显示在下图中(使用Alistair Jones的Arrows在线工具生成的队列的SVG图):

由于这些是队列,我总是从队列的TAIL添加新项目.我知道双关系(下一个/上一个)不是必需的,但它们简化了两个方向的遍历,所以我更喜欢它们.

插入新节点

这是我用来插入新"卡片"的查询:

MATCH (currentList:List)-[currentTailRel:TailCard]->(currentTail:Card) WHERE ID(currentList) = {{LIST_ID}}
CREATE (currentList)-[newTailRel:TailCard]->(newCard:Card { title: {{TITLE}}, description: {{DESCRIPTION}} })
CREATE (newCard)-[newPrevRel:PreviousCard]->(currentTail)
CREATE (currentTail)-[newNextRel:NextCard]->(newCard)
DELETE currentTailRel
WITH count(newCard) as countNewCard
WHERE countNewCard = 0
MATCH (emptyList:List)-[fakeTailRel:TailCard]->(emptyList), 
(emptyList)-[fakeHeadRel:HeadCard]->(emptyList) 
WHERE ID(emptyList) = {{LIST_ID}}
WITH emptyList, fakeTailRel, fakeHeadRel
CREATE (emptyList)-[:TailCard]->(newCard:Card { title: {{TITLE}}, description: {{DESCRIPTION}} })
CREATE (emptyList)-[:HeadCard]->(newCard)
DELETE fakeTailRel, fakeHeadRel
RETURN true

查询可以分为两部分.在第一部分:

MATCH (currentList:List)-[currentTailRel:TailCard]->(currentTail:Card) WHERE ID(currentList) = {{LIST_ID}}
CREATE (currentList)-[newTailRel:TailCard]->(newCard:Card { title: {{TITLE}}, description: {{DESCRIPTION}} })
CREATE (newCard)-[newPrevRel:PreviousCard]->(currentTail)
CREATE (currentTail)-[newNextRel:NextCard]->(newCard) …

有一天,我的数据结构课程教授(Java)说,"好吧,伙计们,我们怎样才能从内存中清除这个n元素双向链表？".我大声说出"将头部和尾部设置为空".他回答说"好的,但这真的从记忆中清除了吗？" 我说"是的,我是这么认为的".

无论如何,他接着说,由于列表中的节点之间有来回传递,所以它并没有真正从内存中清除它.我想我们正在看这样的事情:

        Head                                                                     Tail
null <-[null/data/node 2]-> <-[node1/data/node3]-> <-[node2/data/node4]-> <-[node3/data/null]->null

让我们假设这是Java中典型的双向链表数据结构,其中Node是一个类(内部或单独的类),DoublyLinkedList类中唯一的实例变量是

 Node head;

和

 Node tail;

他说这是因为在列表的内部部分中,每个节点都有一个对下一个节点的引用,并且该节点具有对前一个节点的引用.他说在单链表中不会出现这种情况,因为引用只是"单行道",一旦你失去对第一个引用的引用,它们最终都会被垃圾收集.

当然,课堂上的每个人都分享了他们的观点,但课堂上没有人是我听过的任何人或从中获取编程建议,而且当我在Stack Overflow上提出一个问题与我的教授所说的问题时,我似乎得到了相互矛盾的信息.我.我会说实话,我没有足够的经验来讨论这个问题,但简单地说,我不知道我是否总是相信他所说的一切,因为他在我问过他的一两件事上是错的.

所以,确定

head = null;

和

tail = null;

从内存中清除整个列表？如果是这样,我该怎么验证呢？如果没有,那么摆脱清单的解决方案的一般想法是什么？逐节点删除？请留下您的想法和意见.

我正在尝试用 Java 实现 Knuth 的 Dancing Links 算法。

根据 Knuth 的说法，如果x是一个节点，我可以通过 C 中的以下操作完全取消链接节点：

L[R[x]]<-L[x]
R[L[x]]<-R[x]

并通过以下方式恢复取消链接：

L[R[x]]<-x
R[L[x]]<-x

我的主要方法中做错了什么？

Java中如何实现取消链接和恢复？

这是我的主要方法：

      ///////////////

      DoublyLinkedList newList = new DoublyLinkedList();

      for (int i = 0; i < 81; i++) {
        HashSet<Integer> set = new HashSet<Integer>();
        set.add(i);
        newList.addFirst(set);
      }

      newList.displayList();

      // start at 69
      newList.getAt(12).displayNode();

      //HOW TO IMPLEMENT UNLINK?
      //newList.getAt(12).previous() = newList.getAt(12).next().previous().previous();
      //newList.getAt(12).next() = newList.getAt(12).previous().next().next();

      newList.displayList();

      //HOW TO IMPLEMENT REVERT UNLINK?
      //newList.getAt(12) = newList.getAt(12).next().previous();
      //newList.getAt(12) = newList.getAt(12).previous().next();

      System.out.println();

      ///////////////

这是 DoubleLinkedList 类： …