将节点添加到链接列表的末尾

我一直在尝试将项目添加到链接列表的末尾。我想我对这个概念有一定的把握，但是我很难实现这些代码。特别是，能够遍历链表并找到尾部。这是我到目前为止。我一直在尝试不同的事情。任何帮助，将不胜感激。将节点添加到链接列表的末尾

##include <iostream> 
using namespace std; 


class node 
{ 
public: 
    int data; 
    node *next; 
}; 


class linkedList 
{ 
private: 
    node* ptrHead; 
    node* ptrTail; 

    int size; 

public: 
    linkedList(); //default constructor 
    void display(); 
    void addFront(int); 
    void removeFront(); 
    void addBack(int); 
    void removeBack(); 
}; 

//default constructor 
linkedList::linkedList(){ 
    size = 0; 
    ptrHead = ptrTail = NULL; 
} 
//display linked list 
void linkedList::display(){ 
    node* current = ptrHead; 

    while (current != NULL) { 
     cout << current->data << " "; //display current item 
     current = current->next; //move to next item 
    } 
    cout << size; 
} 
//add item to front of linked list 
void linkedList::addFront(int addData){ 

    node* n = new node; 
    n->next = ptrHead; 
    n->data = addData; 
    ptrHead = n; 

    size++; 
} 
//remove item from front of linked list 
void linkedList::removeFront(){ 

    node* n = ptrHead; 
    ptrHead = ptrHead->next; 
    delete n; 

    size--; 
} 

     void linkedList::addBack(int addData){ ////work in progress 


     node* n = new node; //create new node 
     n->data = addData; //input data 
     n->next = NULL;  //set node to point to NULL 

     if (ptrTail == NULL) // or if (ptrTail == nullptr) 
     { 
      ptrHead = n; 
      ptrTail = n; 
     } 
     else 
     { 
      ptrTail->next = n; 
      ptrTail = n; 
     } 

     size++; 
    } 



    //this is the test code from my main function 
       int main() 
     { 
      //test code 
      linkedList list; 

      list.addFront(40); 
      list.addFront(30); 
      list.addFront(20); 
      list.addFront(10); 
      list.addFront(0); 
      list.addBack(50); 
      list.addBack(60); 

      list.display(); //50 60 7 (the 7 is the count/size of the linked list) 
      cout << endl; 
     }

来源

2014-02-24 JosephK

这不回答你的问题，但你有没有考虑创建一个双向链表？如果将'n-prev'指针添加到'node'，则每次将项添加到列表末尾时，您都不必遍历整个列表。 –

我还没有学过双向链表。我正在努力工作。谢谢你的提示。：） – JosephK

你已经确定了单链表的主要弱点。有一些非常特殊的场景，以线性方式从头到尾遍历，完美地模拟所需的功能。就像，一个foreach块将如何处理每个语句从开始到结束，除非您添加一个退出条件来打破循环。双向链表的工作原理相同，但包含引用和指针。它增加了更多的开销，但在某些特定情况下，与单链表相同的方式很有用。 –

你没有展示你的LinkedList的定义。

所以我只能假设它有数据成员ptrTail和ptrHead。在这种情况下，函数将通过以下方式

void linkedList::addBack(int addData) 
{ 
    node* n = new node; //create new node 
    n->data = addData; //input data 
    n->next = NULL;  //set node to point to NULL 

    if (ptrTail == NULL) // or if (ptrTail == nullptr) 
    { 
     ptrHead = n; 
    } 
    else 
    { 
     ptrTail->next = n; 
    } 
    ptrTail = n; 

    size++; 
}

功能addFront可以定义类似的方式

void linkedList::addFront(int addData) 
{ 
    node* n = new node; //create new node 
    n->data = addData; //input data 

    if (ptrHead == NULL) // or if (ptrHead == nullptr) 
    { 
     ptrTail = n; 
    } 

    n->next = ptrHead; 
    ptrHead = n; 

    size++; 
}

还有一个功能

void linkedList::removeFront() 
{ 
    if (ptrHead != NULL) 
    { 
     if (ptrTail == ptrHead) ptrTail = NULL; 
     node* n = ptrHead; 
     ptrHead = ptrHead->next; 
     delete n; 
     size--; 
    } 
}

来源

2014-02-24 00:39:16

我会很乐意抛出我的答案，并提高这个，如果你巩固'ptrTail = n;'（我知道，它的善变，但它如此接近，你张贴第一..） – WhozCraig

我试着这样实现它，得到一个奇怪的结果。我的输出是0 10 20 30 40，在我将50和60加到后面后，我的输出只有50 60. – JosephK

@JosephK正如我所说的，你没有显示你的类定义。这个错误可能是其他错误的成员函数定义的结果。例如，是否在构造函数中将ptrHead和ptrTail初始化为零。 –

试试这个

node* pCurrent = ptrHead; 
if(pCurrent != NULL){ 
    //find tail 
    while (pCurrent->next != NULL) 
     pCurrent = pCurrent->next; 

    // add new node at end of tail 
    pCurrent->next = n; 
    } else { 
     pCurrent = n; 
    } 
}

来源

2014-02-24 00:31:01 Dinesh

这不起作用。 – JosephK

@JosephK查看我的编辑 – Dinesh

这个工程。非常感谢，先生。我一直试图将我的pCurrent节点分配给我的尾节点，并且我将所有事情混淆在一起。 – JosephK

for(int i=1; i<size; i++) 
    pCurrent = pCurrent->next; 

pCurrent = n;

这将工作。但是您必须将大小保持为链接列表的实际大小。

或者如果您想要始终添加元素，您可以按照以下步骤操作。保留一个额外的节点尾部并添加元素。

if(head == NULL) 
{ 
    head = n; 
    tail = n; 
} 
else 
{ 
    tail->next = n; 
    tail = tail->next; 
}

来源

2014-02-24 00:40:58

将节点添加到链接列表的末尾

回答

相关问题