Skip to content

Instantly share code, notes, and snippets.

@shinnya
Created July 10, 2018 15:50
Show Gist options
  • Save shinnya/291c472df7cc9af018ac172f62f06519 to your computer and use it in GitHub Desktop.
Save shinnya/291c472df7cc9af018ac172f62f06519 to your computer and use it in GitHub Desktop.
Incorrect Doubly Linked List
#include <memory>
#include <string>
#include <iostream>
using namespace std;
template <typename K, typename V>
struct Node
{
K key;
V value;
std::shared_ptr<Node<K, V>> prev;
std::shared_ptr<Node<K, V>> next;
Node(K&& key, V&& value) : key(std::move(key)), value(std::move(value)) {}
};
template <typename K, typename V>
struct List
{
typedef Node<K, V> node_t;
typedef std::shared_ptr<node_t> node_ptr;
List() : head{}, tail{} {}
void insertBefore(
// const std::shared_ptr<T>& is incorrect. we must use std::shared_ptr<T> here.
const node_ptr& node,
const node_ptr& newNode)
{
newNode->prev = node->prev;
newNode->next = node;
if (node->prev) {
node->prev->next = newNode;
} else {
head = newNode;
}
node->prev = newNode;
}
node_ptr head;
node_ptr tail;
};
int main()
{
List<int, string> list;
list.head = std::make_shared<Node<int, string>>(1, "a");
list.insertBefore(
list.head,
std::make_unique<Node<int, string>>(2, "b")
);
list.insertBefore(
list.head,
std::make_unique<Node<int, string>>(3, "c")
);
// we expect the output should be 3 2 1 but get 2 3 2.
cout << list.head->key << endl;
cout << list.head->next->key << endl;
cout << list.head->next->next->key << endl;
return 0;
}
@shinnya
Copy link
Author

shinnya commented Jul 10, 2018

at LINE 38, node and newNode arguments references to the same pointer.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment