用指针实现双向链表 C++

Doubly Linked List Implementation with Pointers C++

提问by Alex Barry

I am currently teaching myself C++ and am attempting to implement a doubly-linked list in C++ using pointers which is partially complete. I am aware that the code currently fails to deal with dangling nodes or output errors, both of which I will implement next. However, the code should atleast be able to construct a list object and add elements to it. Currently, I am getting an error when I attempt to call a constructor for the list, which says that I am requesting a conversion from LinkedList* to non scalar type LinkedList. Why is my list being declared as a pointer? Any help would be much appreciated, thank you!

我目前正在自学 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;
}

LinkedList::~LinkedList()
{
//dtor
}

void LinkedList::addAtFront(int newElement)
{
if (size == 0)
{
    Node temp;
    temp.data.id = newElement;
    temp.data.key = 0;
    head = &temp;
    tail = &temp;
    ++size;
}
else
{
    Node temp;
    temp.data.id = newElement;
    temp.data.key = size;
    temp.next = head;
    head->prev = &temp;
    head = &temp;
    ++size;
}
}

void LinkedList::addAtBack(int newElement)
{
if (size == 0)
{
    Node temp;
    temp.data.id = newElement;
    temp.data.key = 0;
    head = &temp;
    tail = &temp;
    ++size;
}
else
{
    Node temp;
    temp.data.id = newElement;
    temp.data.key = 0;
    tail->next = &temp;
    temp.prev = tail;
    tail = &temp;
    ++size;
}
}

LinkedListTest.cpp
#include "LinkedListTest.h"
#include "LinkedList.h"

int main()
{
LinkedList list = new LinkedList();
list.addAtFront(0);
}

回答by Hyman

The error means that somewhere you have a LinkedList list declared not as a pointer, to which you assign a new LinkedList()which is of type LinkedList*(and not LinkedList). It should be:

该错误意味着您在某处有一个 LinkedList 列表声明为不是指针，您将 a new LinkedList()which 类型LinkedList*（而不是LinkedList）分配给该列表。它应该是：

LinkedList* list = new LinkedList(); // I declare a pointer to a list
list->addAtFront(0); // I call a method on a pointer to an object

or

或者

LinkedList list;
list.addAtFront(0);

They are two different types which are allocated in two different storages and this is important, keep reading.

它们是两种不同的类型，分配在两个不同的存储中，这很重要，请继续阅读。

What I see more importantly is that when you use dynamically allocated memory you should take case of actually allocate on heap objects that should persist the scope in which they are declared.

我看到更重要的是，当您使用动态分配的内存时，您应该考虑在堆对象上实际分配的情况，这些对象应该保留声明它们的范围。

More specifically, this:

更具体地说，这个：

{
  Node temp;
  ..
  head = &temp;
  ..
}

This will cause problems because tempis declared as automatic storage on stack, which means that once you obtained its address and assign it to heador tailor whatever, that address won't be valid anymore once the scope exited. You should allocate it on heap:

因为这将导致问题temp被声明为堆栈自动存储，这意味着一旦你得到它的地址，并将其分配给head或tail也好，该地址将不再有效，一旦退出范围。您应该在堆上分配它：

Node temp = new Node(value, id);
head = temp;
tail = temp;
++size;

Mind that this requires that you clean up memory by yourself from the heap when the Nodeis not needed anymore.

请注意，这要求您在Node不再需要时自己从堆中清理内存。

回答by Alex P

new returns a pointer to a LinkedList object, which you are attempting to assign to a LinkedList object, instead of a pointer.

new 返回一个指向 LinkedList 对象的指针，您正试图将其分配给 LinkedList 对象，而不是一个指针。

LinkedList list = new LinkedList();

should read

应该读

LinkedList list;

回答by abhishek kumar

Try this completely implemented doubly linked list:

试试这个完全实现的双向链表：

#include <stdio.h>

struct node{
int data;
struct node *next,*prev;
};

struct node *head=NULL;

void insert(int data, int position)
{
    struct node *newNode=malloc(sizeof(struct node));
    newNode->data=data;

    if(position<1)
    {
      printf("Invalid Insertion Position \n");
      return;
    }
    if(head==NULL && position==1)
    {
        newNode->next=NULL;
        newNode->prev=NULL;
        head=newNode;
    }
    else if(head==NULL && position!=1)
    {
        printf("Invalid Insertion Position \n");
    }
    else if(position==1)
    {
        newNode->next=head;
        newNode->prev=NULL;
        if(head->next!=NULL)
        {
           head->next->prev=newNode;
        }
        head=newNode;
    }
    else
    {
        int i=0;
        struct node *temp=head;
        while(temp->next!=NULL && i<position-2)
        {
            i++;
            temp=temp->next;
        }
        if(i<position-2)
        {
            printf("Invalid Insertion Position \n");
        }
        else
        {
        newNode->next=temp->next;
        temp->next=newNode;
        newNode->prev=temp;
        if(temp->next!=NULL)
        {
            temp->next->prev=newNode;
        }
        }

    }
}

void delete(int position)
{
    int i=0;
    if(position<1)
    {
        printf("Invalid Position of Deletion \n");
        return;
    }
    if(head==NULL)
    {
        return;
    }
    if(position==1)
    {
        head=head->next;
        if(head!=NULL)
        {
        head->prev=NULL;
        }
    }
    else
    {
        struct node *temp=head;
        while(temp->next->next!=NULL && i<position-2)
        {
            i++;
            temp=temp->next;
        }
         if(i<position-2)
            {
                printf("Invalid Position of Deletion \n");
                return;
            }
        else
            {
                temp->next=temp->next->next;
                if(temp->next!=NULL)
                temp->next->prev=temp;
            }
    }
}



void printlist()
{
    if(head==NULL)
    {
        printf("Empty List!! \n");
        return;
    }
    struct node *temp=head;

    while(temp!=NULL)
    {
        printf("%d",temp->data);
        printf("\t");
        temp=temp->next;
    }
    printf("\n");
}

int main()
{
    int t;
    printf("Enter number of Test Cases: \t");
    scanf("%d", &t);
    printf("\nEnter Queries in this format: \n");
    printf("For Insertion: \t I data position \n");
    printf("\tEx:\t I 25 5 \n");
    printf("For Deletion: \t D position \n");
    printf("\tEx:\t D 2 \n\n");

    while(t--)
    {
        char c;
        int a,b;
        printf("Enter query: \t");
        scanf("%c", &c);
        scanf("%c", &c);

        if(c=='I')
        {
            scanf("%d %d", &a,&b);
            insert(a,b);
        }
        else if(c=='D')
        {
           scanf("%d", &a);
           delete(a);
        }
        printlist();
    }

}

回答by user6897426

I think you should implement two classes:

我认为你应该实现两个类：

1. Doubly linked lists with a sentinel: Double_sentinel_list, and
2. Doubly linked nodes: Double_node.

1. 带有标记的双向链表：Double_sentinel_list，和
2. 双链节点：Double_node.

Member Variables. Constuctors,Destructors:

成员变量。构造函数，析构函数：

int size() const; 
  //Returns the number of items in the list.
bool empty() const;  
  // Returns true if the list is empty, false otherwise.
Type front() const;  
  // Retrieves the object stored in the node pointed to by the next pointer of the head sentinel. This function throws a underflow if the list is empty. 
Type back() const;   
  // Retrieves the object stored in the node pointed to by the previous pointer of the tail sentinel. This function throws a underflow if the list is empty.
Double_node<Type> *head() const;  
  // Returns the head pointer.
Double_node<Type> *tail() const;  
  // Returns the tail pointer.
int count( Type const & ) const;  
  // Returns the number of nodes in the linked list storing a value equal to the argument. Mutators

This class has seven mutators:

这个类有七个mutator：

void swap( Double_sentinel_list & );  
  // The swap function swaps all the member variables of this linked list with those of the argument.
Double_sentinel_list &operator=( Double_sentinel_list & );  
  // The assignment operator makes a copy of the argument and then swaps the member variables of this node doubly linked sentinel list those of the copy.
void push_front( Type const & );  
  // Creates a new Double_node<Type> storing the argument, the next pointer of which is set to the next pointer of the sentinel and the previous pointer is set to point to the sentinel. Theprevious pointer of what was the first node is set to the new node.
void push_back( Type const & );  
  //  Similar to push_front, this places a new node at the back of the list.
Type pop_front();  
  // Delete the first non-sentinel node at the front of the linked list and the previous and next pointers of any other node (including the sentinels) within the list. Return the object stored in the node being popped. Throw an underflow exception if the list is empty.
Type pop_back();  
  // Similar to pop_front, delete the last non-sentinel node in the list. This function throws a underflow if the list is empty.
int erase( Type const & );  
  // Delete the first node (from the front and other than the sentinals) in the linked list that contains the object equal to the argument (use == to to test for equality with the retrieved element). Update the previous and next pointers of any other node (including possibly the sentinels) within the list. Return the number of nodes that were deleted. 

回答by Igor Tandetnik

Either

任何一个

LinkedList list;
list.addAtFront(0);

or

或者

LinkedList* list = new LinkedList();
list->addAtFront(0);
delete list;