我目前正在自学C++,并尝试使用部分完成的指针在C++中实现双向链表.我知道代码当前无法处理悬空节点或输出错误,我将在下面介绍这两个节点.但是,代码应该至少能够构造一个列表对象并向其添加元素.目前,当我尝试调用列表的构造函数时,我收到一个错误,表示我正在请求从LinkedList*到非标量类型LinkedList的转换.为什么我的列表被声明为指针？非常感谢任何帮助,谢谢!
LinkedList.h
#ifndef LINKEDLIST_H
#define LINKEDLIST_H
struct dataElement {
int key;
int id;
};
struct Node
{
dataElement data;
Node* next;
Node* prev;
};
class LinkedList
{
public:
/** Default constructor */
LinkedList();
/** Default destructor */
virtual ~LinkedList();
void addAtFront(int newElement);
void addAtBack(int newElement);
int removeTop();
int removeBottom();
int getTop();
int getBottom();
int findKey(int keyToFind);
protected:
private:
Node* head;
Node* tail;
int size;
};
#endif // LINKEDLIST_H
LinkedList.cpp
#include "LinkedList.h"
#include <iostream>
#include <stdlib.h>
LinkedList::LinkedList()
{
size = 0; …我创建了双向链表，并设法从头到尾打印它，但是我在向后打印时遇到了麻烦。我在“current = current->prev”行中遇到分段错误，我不明白为什么。
current = head;
while (current) {
printf("%p\t%s\t%d\n", current, current->name, current->age);
current = current->next;
}
current = current->prev;
while (current) {
printf("%p\t%s\t%d\n", current, current->name, current->age);
current = current->prev;
}
我找到了解决这个问题的方法：
current = head;
while (current) {
printf("%p\t%s\t%d\n", current, current->name, current->age);
current = current->next;
}
current = head;
while (current->next) current = current->next;
while (current) {
printf("%p\t%s\t%d\n", current, current->name, current->age);
current = current->prev;
}
但是，我仍然不明白为什么我的方法不起作用。如果有人可以解释这一点，我将不胜感激。
我必须尽可能高效地编写一个程序，将给定的节点插入到已排序的 LinkedList 中。我在想二分搜索在平均和最坏情况下如何比线性更快，但是当我搜索它时，运行时间是 O(nlogn)？我应该在单链表上进行线性搜索还是在双链表上进行二分搜索，为什么那个（选择的）更快？
另外，对于双向链表，二进制搜索算法如何 > O(logn)？（没有人推荐 SkipList，我认为它们违反了规则，因为我们有另一种严格针对该数据结构的实现）
我在C++中使用模板编写了一个双向链表的简单实现.但是,我在复制构造函数和赋值运算符方面遇到了一些问题.我的代码给了我分段错误,我不知道如何修复它以及错误在哪里(问题在于复制构造函数和赋值运算符):
#include <iostream>
using namespace std;
template <class T>
class MyNode
{
public:
MyNode(const T &e = T(), MyNode *n = NULL, MyNode *p = NULL) : element(e), next(n), previous(p) {}
~MyNode() {}
T element;
MyNode *next;
MyNode *previous;
};
template <class T>
class MyList
{
private:
MyNode<T> *head;
MyNode<T> *tail;
public:
MyList()
{
head = new MyNode<T>();
tail = new MyNode<T>();
}
~MyList()
{
clear();
delete head;
delete tail;
}
MyList(const MyList& otherList)
{
while (otherList.head->next!=NULL)
{
MyNode<T> *curr …我有一个不再需要的指针列表。要删除所有这些，我通常可以迭代列表：
for (T* ptr: mylist) {
delete ptr;
}
或者我可以删除第一个或最后一个元素，直到列表为空：
while (!mylist.empty()) {
delete mylist.front(); //or mylist.back()
mylist.pop_front(); //or mylist.pop_back()
}
对于性能和清晰度而言，首选方式是什么？
我正在学习Java中的双链表,我找到了一个关于删除具有特定键的节点的教程.
这是代码:
public Node deleteKey(int key) {
Node current = first;
while (current.getData() != key) {
current = current.getNext();
if (current == null) {
return null;
}
}
if (current == first) {
first = current.getNext();
} else {
current.getPrevious().setNext(current.getNext());
}
if (current == last) {
last = current.getPrevious();
} else {
current.getNext().setPrevious(current.getPrevious());
}
return current;
}
我想问你这段代码是否正确.在我看来,这是不正确的,因为他还需要这样做:
current.setNext(null);
current.setPrevious(null);
我一直想知道这个问题已经有一段时间了，在SO上还没有找到一个好的答案。
我想做的是在链表中找到一个元素并立即将其删除。如果我自己构建链表，那将很容易，因为我只是遍历双重链表：
-> N1 <-> N2 <-> N3 <-> N4 <-> N5 <-
当找到例如N3时，可以更改node.previous和node.next指针，例如：
-> N1 <-> N2 <-> N4 <-> N5 <-
如果元素在中间，则大约需要2个步骤。
是否有适当的方法可以做到这一点java.util.LinkedList<Integer>？
对我来说不足的方法是：
Integer found = null;
for(Integer elem : list){
if(hasCertainProperty(elem)){
found = elem;
}
}
if(found != null){
list.remove(found);
}
如果该元素是列表中的中间元素（双链表，则从理论上讲，如果知道索引，则可以从列表末尾进行搜索），它最多需要大约n / 2 + n / 2 = n个步长。而在自制遍历中，只需要n / 2步。
我知道这2种方法和其他方法都在O（n）中，但是您知道，有时n / 2在实践中会有所不同。
谢谢你的帮助。
在尝试用 C 实现双向链表时，我注意到以下代码片段会在 macOS 10.11 El Capitan 上引发分段错误。然而，当在 Linux 或 Haiku 中测试时，它会愉快地运行，产生预期的结果。
#include <stdio.h>
#include <stdlib.h>
typedef struct node_structure {
int data;
struct node_structure *prev;
struct node_structure *next;
} *node;
node createNode(int value) {
node newNode = (node) malloc(sizeof(node));
if (newNode != NULL) {
newNode->data = value;
newNode->prev = NULL;
newNode->next = NULL;
}
return newNode;
}
void displayLinkedList(node linked_list) {
node cursor = linked_list;
while (cursor != NULL) {
printf("DATA: %d \tTHIS:%p \tPREV:%p \tNEXT:%p\n", cursor->data, (void*)cursor, (void *)cursor->prev, (void …c macos segmentation-fault data-structures doubly-linked-list
我正在尝试使用 OCaml 类型声明来实现一个循环双向链表。这是我所拥有的：
type 'a cList =
{
mutable value : 'a;
mutable left : 'a cList option;
mutable right : 'a cList option
}
;;
当我需要声明包含单个元素的第一个列表时，问题就出现了。因为元素在被赋值之前不能被引用，所以我不能让单元格的左右成员指向它自己。到目前为止，我唯一的解决方法是允许左右成员为 option 类型，将它们设置为 None 然后修改它们，使它们指向单元格本身。
let unitClist v = let a = {
value = v;
left = None;
right = None
}
in
a.left <- Some a;
a.right <- Some a;
a
;;
它可以工作，但是当您确定有一个值时，必须使用选项类型有点绑定。有没有更好的方法来做到这一点？提前致谢。
如果我从头开始开发链表，我可以在我的业务实体类中存储一个指向 Node 对象的指针，并实现常量 O(1) remove和insertAfter操作。在 Java 标准库实现中，它们是 O(n)，在处理大型数据集时可能会有很大差异。
为什么他们不只是公开 Node 类并在其中封装一些细节仍然使类本身（可能通过接口）可访问？这将使 LinkedList 更加灵活。
我们有像Apache Commons 或 Guava 中的FlexibleLinkedList 之类的东西吗？