双向链表 class
Doubly linked list class
我正在尝试制作双重 linked 列表。函数 push(int x) 应该向列表中添加一个节点并使 link 正确。我使用:
class Node {
public:
int value;
Node* next;
Node* prev;
public:
Node() {}
void set_value(int x) { value = x; }
void set_next(Node* x) { next = x; }
void set_prev(Node* x) { prev = x; }
Node* get_next() { return next; }
Node* get_prev() { return prev; }
};
class deque {
public:
Node* head;
Node* tail;
public:
deque() { head = NULL; tail = NULL; }
void push(int x) {
Node* n = new Node();
n->set_value(x);
n->set_next(NULL);
n->set_prev(NULL);
Node* t = head; //link to the next node
if (t == NULL) {
head = n;
} else {
while (t->get_next() != NULL) {
t = t->get_next();
}
t->set_next(n);
}
}
};
正如我测试的那样,将一个节点连接到下一个节点的部分工作正常,但我在将节点连接到前一个节点时遇到了一些问题。想到的是第一个的变体:
Node* t = tail;
if (t == NULL) {
tail = n;
} else {
while (t->get_prev() != NULL) {
t = t->get_prev();
}
t->set_prev(n);
}
但是通过使用这个,尾节点总是当前的n节点,如果只有节点n是队列中的唯一节点......我该怎么办?非常感谢
绘图总是有助于处理此类数据结构。您目前拥有的:
您正确设置了 t
的 next
:t->set_next(n);
。缺少的是它下面的箭头,它是:n->set_prev(t)
.
一般来说,在处理 doubly-linked 列表时,对 set_next
的调用应该总是(大部分时间)伴随着对 [=14= 上的 set_prev
的调用]的说法。这是因为 doubly-linked 列表的 属性:
x->next == y
暗示y->prev == x
,y->prev == x
暗示x->next == y
。
我正在尝试制作双重 linked 列表。函数 push(int x) 应该向列表中添加一个节点并使 link 正确。我使用:
class Node {
public:
int value;
Node* next;
Node* prev;
public:
Node() {}
void set_value(int x) { value = x; }
void set_next(Node* x) { next = x; }
void set_prev(Node* x) { prev = x; }
Node* get_next() { return next; }
Node* get_prev() { return prev; }
};
class deque {
public:
Node* head;
Node* tail;
public:
deque() { head = NULL; tail = NULL; }
void push(int x) {
Node* n = new Node();
n->set_value(x);
n->set_next(NULL);
n->set_prev(NULL);
Node* t = head; //link to the next node
if (t == NULL) {
head = n;
} else {
while (t->get_next() != NULL) {
t = t->get_next();
}
t->set_next(n);
}
}
};
正如我测试的那样,将一个节点连接到下一个节点的部分工作正常,但我在将节点连接到前一个节点时遇到了一些问题。想到的是第一个的变体:
Node* t = tail;
if (t == NULL) {
tail = n;
} else {
while (t->get_prev() != NULL) {
t = t->get_prev();
}
t->set_prev(n);
}
但是通过使用这个,尾节点总是当前的n节点,如果只有节点n是队列中的唯一节点......我该怎么办?非常感谢
绘图总是有助于处理此类数据结构。您目前拥有的:
您正确设置了 t
的 next
:t->set_next(n);
。缺少的是它下面的箭头,它是:n->set_prev(t)
.
一般来说,在处理 doubly-linked 列表时,对 set_next
的调用应该总是(大部分时间)伴随着对 [=14= 上的 set_prev
的调用]的说法。这是因为 doubly-linked 列表的 属性:
x->next == y
暗示y->prev == x
,y->prev == x
暗示x->next == y
。