标签: doubly-linked-list

我有一个双链表,需要快速插入和删除.我可以在任何一个方向横向移动整个东西以找到插入或移除的位置,但有没有更聪明的方法来找到插入或移除点？首先想到的是二进制搜索,但由于它是一个没有索引(不是数组)的链表,我不知道如何跳转到我的链表.

什么是正确的方法,使插入和删除最快？

我创建了一个双链表类,并尝试将它与我创建的Vector类一起使用,以便创建链接列表的向量,但是在程序结束时,我似乎得到一个错误 malloc: *** error for object 0x100100be0: pointer being freed was not allocated ,我假设已经与析构函数有关,也就是Xcode指向我的地方.我该如何规避这个？我认为我的析构函数工作正常,但我想我错了.

测试文件:

#include <iostream>
#include <string>
#include "Vector.h"
#include "doubleLL.h"

using namespace std;

int main (int argc, const char * argv[])
{

    Vector<double_llist<string> > listWords(27);
    double_llist<string> numbers;
    numbers.push_back("one");
    numbers.push_back("two");
    numbers.push_back("three");
    listWords[0] = numbers;
    listWords[0].print();
}

doubleLL.h:

#ifndef DOUBLELL_H
#define DOUBLELL_H
#include <iostream>
using namespace std;

template <class T>
class double_llist {
private:
    struct node {
        T data;
        node* prev;
        node* next;
        node(T t, node* p, node* n) …

I have a ordered binary tree:
              4
              |
          |-------|
          2       5
          |
      |-------|
      1       3

叶子指向null.我必须创建一个看起来像双重链接的列表

1<->2<->3<->4<->5

(显然5应该指向1)

节点类如下:

class Node {
    Node left;
    Node right;
    int value;

    public Node(int value)
    {
        this.value = value;
        left = null;
        right = null;
    }
}

如您所见,双重链接列表也是有序(排序)的.

问题:我必须在树中创建链表而不使用任何额外的指针.该left树的指针应该是previous列表的指针和right树的指针应该是next列表的指针.

我想的是:由于树是有序树,因此遍历遍历会给我一个排序列表.但在进行inorder遍历时,我无法看到,在何处以及如何移动指针以形成双向链表.

PS我检查了这个问题的一些变化,但没有一个给我任何线索.

typedef struct tape
{
    char symbol;
    struct tape *next;
    struct tape *prev;
}tape;

tape *pt;    

void GenerateInputTape(int n)
{
    int i;

    pt=(tape*)malloc(sizeof(tape));

    pt->symbol='B';

    pt->prev=NULL;
    pt->next=(tape*)malloc(sizeof(tape));
    pt=pt->next;

    for(i=0;i<2*(n+1);i++)
    {   
        if(i < (2*n/2))
            pt->symbol='0';
        else
            pt->symbol='1';

        pt->prev=pt;
        pt->next=(tape*)malloc(sizeof(tape));
        pt=pt->next;
    }

    pt->symbol='B';

    pt->next=NULL;
}

void ShowTape()
{
    //Move tape to the beginning
    while (pt->prev != NULL)
        pt=pt->prev; //crash point

    //List out all of the elements
    while ((pt->next) != NULL)
    {   
        printf("%c",pt->symbol);
        pt=pt->next;
    }
    puts("\n");
}

这是一个程序的代码片段,旨在创建一个双向链表,用B0 ... n011 ....(n + 1)1B字符填充并打印它们.不幸的是,它在穿越时崩溃了.为什么？

turing_machine.exe中0x771a15de处的未处理异常:0xC0000005:访问冲突读取位置0xcdcdcdd5.

我曾经有一位教授告诉我,这std::stack通常是使用双链表实现的,如果您只需要访问顶部,这将是多余的.

他的结论是用一个std::vector或一个链表实现的用户定义的堆栈结构可以节省内存空间.

无论哪种方式,我都可能使用STL版本(没有浪费精力),但std::stack真的浪费了这样的记忆吗？

插入到我的链接列表中会导致分段错误，我不确定为什么。这是一个 int 链表。它有时有效，有时则无效。我看不出哪里会出错？也许这与我创建新链表的时间有关。由于链接列表插入最后一个方法在文件读取期间起作用，但在我创建新列表时不起作用。

LinkedList* createLinkedList()
{
    LinkedList* list;

    list = (LinkedList*)malloc(sizeof(LinkedList));
    list->head = NULL;
    list->tail = NULL;
    list->length = 0;

    #ifdef DEBUG
    printf("Linked list. Creation of list complete. Checking list length. %d \n", list->length);
    #endif

    return list;
}

void insertLast(LinkedList* list, int entry)
{
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->data = entry;

    /*If list is empty*/
    if(list->length == 0)
    {
        list->head = newNode;
        list->tail = newNode;
    }
    else
    {
        newNode->prev = list->tail;
        /*if this is the second item in the list*/ …

使用我当前的方法我得到一个运行时错误,"列出iter not derefrencable".for循环看起来像:

for (iter = the_list.end(); iter != the_list.begin(); iter--)
{
    if (assignment >= (*iter)){ // If the assignment being added is greater than assignment being pointed to in the list, add it after
                                // the assignment being pointed to
        if (!(assignment == (*iter))) // If the assignment being added is not a duplicate, add it
        {
            iter++; // Increment the iterator to add the assignment to place after the one it was compared to
            the_list.insert(iter, assignment); // Insert …

我试图扭转循环双向链表,看起来像这样:

这是我的Node类:

       private class Node<T>
   {
       public T Data { get; set; }
       public Node<T> PreviousNode { get; set; }
       public Node<T> NextNode { get; set; }

       public Node(object data, Node<T> next, Node<T> previous)
       {
           Data = (T) data;
           PreviousNode = previous;
           NextNode = next;
       }
   }

这是我的链接列表类的一部分,这里是我的反向功能存储:

 public class DoublyLinkedList<T> :IList<T>
{
    private Node<T> headerNode;
 public DoublyLinkedList()
{
        headerNode = new Node<T>(null, null, null);

        headerNode.NextNode     = headerNode;
        headerNode.PreviousNode = headerNode;
        Count = 0;
}

   public void Insert(int index, T …

由于LinkedList的Java实现是双向链表.如果说传递给get get(int index)方法的索引超过了链表的中间,那么它是否更有意义呢？该值是使用列表尾部的降序迭代器获得的？

这会发生吗？

如果不是为什么？

示例说我有一个如下所示的链接列表:

head                                 tail
  A <-> B <-> C <-> D <-> E <-> F <-> G 

我说linkedList.get(5)得到第二个linkList中的最后一个元素.java会在内部使用降序迭代器(从尾部开始)来检索F,还是不行？由于5已超过链表的中间位置.

我们学会了如何在课堂上实现单链表.我们的教授提到我们做了双重链表,但显然很容易,他真的没有详细解释如何做到这一点.我非常擅长处理单链表,但是有人可以告诉我如何制作双重链表吗？

是否可以使用两个元素在Java中创建双向链表.一个元素必须是String,而另一个元素必须是Int.

这是可能的,如果可以的话怎么样？

谢谢