All geek questions in one place

Any improvements over my linked list method?

I am constantly writing a program to improve my knowledge of linked lists and how they function. I was wondering if some of you could look at my code and notice any errors that you are familiar with, or any errors in general. Functions work for my test functions, but obviously I have not tested all possible scenarios.

    // LinkedList.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
#include <iostream>

using std::cout;
using std::cin;
using std::endl;

struct node
{
    int value;
    node* next;
};

node* push(node*, int);
node* pop(node*);
node* pop(node*, int);
node* insert(node*, int, int);
void printList(const node*);

int _tmain(int argc, _TCHAR* argv[])
{
    node* head = NULL;

    for(int i = 1; i <= 15; ++i)
    {
        head = push(head, i);
    }

    for(int j = 14; j >= 0; j = j - 2)
    {
        head = pop(head, j);
        printList(head);
    }

    head = pop(head);
    head = insert(head, 4, 27);
    printList(head);
    cin.ignore();
}

node* push(node* read, int val)
{
    node* write = read;
    if(read == NULL)
    {
        read = new node;
        read->next = NULL;
        read->value = val;
        cout << "Node Head: " << read->value << endl;
        return read;
    }
    else
    {
        while(read->next != NULL)
        {
            read = read->next;
        }
        read->next = new node;
        read->next->next = NULL;
        read->next->value = val;
        read = read->next;
        cout << "Node Link: " << read->value << endl;
        return write;
    }
}

node* pop(node* read)
{
    node* write = read;
    if(read->next == NULL)
    {
        delete read;
        read = NULL;
        return write;
    }
    else
    {
        while(read->next != NULL)
        {
            if(read->next->next == NULL)
            {
                cout << "Pop: " << read->next->value << endl;
                delete read->next;
                read->next = NULL;
            }
            else
            {
                read = read->next;
            }
        }
        return write;
    }
}

node* pop(node* read, int pos)
{
    node* write = read;
    if(read->next == NULL)
    {
        delete read;
        return write;
    }
    else
    {   
        if(pos == 0)
        {
            node* old = read;
            cout << "Pop: " << read->value << endl;
            read = read->next;
            delete old;
            return read;
        }
        else
        {
            for(int i = 0; i < (pos - 1); i++)
            {
                read = read->next;
            }
            node* old = read->next;
            cout << "Pop: " << old->value << endl;
            read->next = read->next->next;
            delete old;
            return write;
        }
    }
}

node* insert(node* read, int pos, int val)
{
    node* write = read;
    for(int i = 0; i < (pos - 1); i++)
    {
        read = read->next;
    }
    node* ins = new node;
    ins->value = val;
    cout << "Insert: " << ins->value << endl;
    ins->next = read->next;
    read->next = ins;
    return write;
}

void printList(const node* read)
{
    if(read != NULL)
    {
        cout << "List Item: " << read->value << endl;
        printList(read->next);
    }
}

/****************OUTPUT*********************
Node Head: 1
Node Link: 2
Node Link: 3
Node Link: 4
Node Link: 5
Node Link: 6
Node Link: 7
Node Link: 8
Node Link: 9
Node Link: 10
Node Link: 11
Node Link: 12
Node Link: 13
Node Link: 14
Node Link: 15
Pop: 15
List Item: 1
List Item: 2
List Item: 3
List Item: 4
List Item: 5
List Item: 6
List Item: 7
List Item: 8
List Item: 9
List Item: 10
List Item: 11
List Item: 12
List Item: 13
List Item: 14
Pop: 13
List Item: 1
List Item: 2
List Item: 3
List Item: 4
List Item: 5
List Item: 6
List Item: 7
List Item: 8
List Item: 9
List Item: 10
List Item: 11
List Item: 12
List Item: 14
Pop: 11
List Item: 1
List Item: 2
List Item: 3
List Item: 4
List Item: 5
List Item: 6
List Item: 7
List Item: 8
List Item: 9
List Item: 10
List Item: 12
List Item: 14
Pop: 9
List Item: 1
List Item: 2
List Item: 3
List Item: 4
List Item: 5
List Item: 6
List Item: 7
List Item: 8
List Item: 10
List Item: 12
List Item: 14
Pop: 7
List Item: 1
List Item: 2
List Item: 3
List Item: 4
List Item: 5
List Item: 6
List Item: 8
List Item: 10
List Item: 12
List Item: 14
Pop: 5
List Item: 1
List Item: 2
List Item: 3
List Item: 4
List Item: 6
List Item: 8
List Item: 10
List Item: 12
List Item: 14
Pop: 3
List Item: 1
List Item: 2
List Item: 4
List Item: 6
List Item: 8
List Item: 10
List Item: 12
List Item: 14
Pop: 1
List Item: 2
List Item: 4
List Item: 6
List Item: 8
List Item: 10
List Item: 12
List Item: 14
Pop: 14
Insert: 27
List Item: 2
List Item: 4
List Item: 6
List Item: 8
List Item: 27
List Item: 10
List Item: 12
*******************************************/
+3
source share
5 answers

Well, firstly, for general use you should use the standard library: std:vectoror if you really need a linked list, std::list<>.But, since this is a self-learning exercise, we will skip this.

: , , ? Cout

, , :

    read = new node;    
    read->next = NULL;    
    read->value = val;

node next null. , :

    read = new node(val);

: pop() :

node* write = read; 
if(read->next == NULL) 
{ 
    delete read; 
    read = NULL; 
    return write; 
}

read null - , . write, read, .

, ++ Object-oreitned: cout, C, new delete. , . , List, node .

+8

node , , "". node, . "", , .

+5

"push" , :

  • 1- "", "",

  • "if (read == NULL)". (, , @James)

  • : " node " val "," "," , head = new; else tail → next = new "

+1

C-style. ++ Node . . . , :

  • , . , pos ( > )?

     node* insert(node* read, int pos, int val)
  {
     node* write = read;
     for(int i = 0; i < (pos - 1), read <> NULL; i++) 
     {// you should make the for stop if it hits the bottom of the list
         read = read->next; 
     }
     if (read == NULL) return NULL
     node* ins = new node;
     ins->value = val;
     cout << "Insert: " << ins->value << endl;
     ins->next = read->next;
     read->next = ins;
     return write;
 }

  • , . , node → next- > next, .

      node* pop(node* read)
  {
      node* write = read;
      if(read->next == NULL)
      {
          delete read;
          read = NULL;
          return write;
      }
      else
      {
          while(read->next != NULL)
          {
              if(read->next->next == NULL)
              {
                  cout << "Pop: " << read->next->value << endl;
                  delete read->next;
                  read->next = NULL;
              }
              else
              {
                  read = read->next;
              }
          }
          return write;
      }
  }

:

     node* pop(node* head)
     {
        if (head == NULL) return;

        node* previous = NULL;
        node* returnVal = head;

        while (head->next != NULL)
        {
            previous = head;
            head = head->next;
        }
        if (previous != NULL)
        {
            previous->next = NULL;
            delete head;
        }
        else //we need to pop out the head :)
        {
            delete head;
            returnVal = null;
        }
        return returnVal;
     }

, . .. ++ :

void SingleLinkedList::RemoveElement(TInfo value)
{
    Node* cursor = mHead;
    Node* lastCursor = NULL;

    if (cursor != NULL) while (cursor->GetNext() != NULL && cursor->GetInfo() != value) 
    {
        lastCursor = cursor;
        cursor = cursor->GetNext();
    }
    if (cursor->GetInfo() == value)
    {
        lastCursor->SetNext(cursor->GetNext());
        delete cursor;
    }
}

:

#define NULL 0
typedef int TInfo;

class Node
{
private:
    TInfo info;
    Node* next;
public:

    Node()                          {info = 0; next = NULL;}
    Node(TInfo iInfo, Node* iNode)  {info = iInfo; next = iNode;}
    ~Node()                         {info = 0; next = NULL;}

    TInfo GetInfo() const           {return info;}
    Node* GetNext() const           {return next;}

    void SetInfo(TInfo value)       {info = value;}
    void SetNext(Node* pValue)      {next = pValue;}
};

class SingleLinkedList
{
private:
    Node* mHead;
    int mCount;

    void RecursiveRemove(Node* iNode);

public:
    SingleLinkedList();
    ~SingleLinkedList() {mHead = NULL;};

    int Count() const               {return mCount;}
    Node* const GetHead() const     {return mHead;}

    void ClearList();
    void AddHeadElement(TInfo value);
    void AddTailElement(TInfo value);
    void RemoveElement(TInfo value);
    bool SearchElement(TInfo value, int &pos);
};

void PrintList (SingleLinkedList const& list);

, . :)

+1

C, void * , :

struct Node
{
    void * p_data;
    struct Node * next;
};

, ++, , template . A template . ():

template <class Data_Type>
struct Node
{
    Data_Type data;
    Node *    next;
};

As other people have said, you must have a List class or structure. This will help users distinguish between instances. In C-Style, this structure will be passed to the list methods (therefore, list methods know which list to work for).

struct List_Header
{
    struct Node * head;
    struct Node * tail;
    unsigned int  size; // Quantity of nodes
};

void List_Push(List_Header * p_header, void * data)
{
  if (p_header)
  {
    // Create a node, prepend to list, etc.
  }
  return;
}

To use the list:

List_Header    my_list;
unsigned int *   my_data(new int(1));
List_Push(&my_list, my_data);
+1
source

Source: https://habr.com/ru/post/1756594/

More articles:


All Articles