C++

Forum

 
Linked List questions

rabster (227)
So far I've made a linked list with relatively little help, which is why I now need it. My linked list "works" but to me doesn't look very efficient. For instance, in both my insert and delete functions I have to cycle through the whole list starting at the head to add in or delete a value. Is it possible I could do it a more efficient/better way? Pretty much what could I do to make this better. Thanks in advance!
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
 
#include <iostream>
#include <string>
#include <typeinfo>
using namespace std;
class linkedList {
private:
    typedef linkedList link;
    unsigned int amount;
    unsigned int counter;
    link* node;
    link* head;
    link* tail;
    link* linker;
    link* cycle;
    link* destroy;
    int info;
public:
    linkedList(int value);
    linkedList();
    ~linkedList();
    void addNode(int value) {
      counter++;
      node = new link;
      node->info = value;
      node->linker = NULL;
      tail->linker = node;
      tail = node;
    }
    void insertNode(const int value, const unsigned int Aindex) {
        try {
            if (Aindex > counter) { throw string("Error cannot insert node between unknown values"); }
            node = new link;
            amount = 0;
            counter++;
            node->info = value;
            cycle = head;
            while(amount < Aindex) {
              amount++;
              cycle = cycle->linker;
            }
            node->linker = cycle->linker;
            cycle->linker = node;
            amount = 0;
        }
        catch(string &error) {
            cerr << error << endl;
        }
    }
    void deleteNode(const unsigned int Aindex) {
      try {
        if (Aindex > counter) { throw string("Error cannot delete node between unknown values"); }
        amount = 0;
        counter--;
        cycle = head;
        while(amount < (Aindex - 1)) {
          cycle = cycle->linker;
          amount++;
        }
        destroy = cycle->linker;
        cycle->linker = destroy->linker;
        delete destroy;
        amount = 0;
      }
      catch(string &error) {
        cerr << error << endl;
      }
    }
    void showElements() {
      cycle = head;
      while(cycle->linker != NULL) {
        cout << "Element " << amount << ": " << cycle->info << '\n';
        amount++;
        cycle = cycle->linker;
      }
      cout << "Element " << amount << ": " << cycle->info << '\n';
    }
    int elementAmount() {
      return this->counter;
    }
};
linkedList::linkedList(int value) {
  amount = 0;
  counter = 1;
  node = new link;
  node->info = value;
  node->linker = NULL;
  head = node;
  tail = node;
}
linkedList::linkedList() {
  
}
linkedList::~linkedList() {
  
}
int main()
{
  char response;
  int x;
  int val;
  int eleCount = 1;
  cout << "What value would you like your linked list to start with: ";
  cin >> x;
  linkedList a(x);
  cout << "Keep entering in values to grow your linked list, enter in 1337 when you would like to quit\n";
  while(x != 1337) {
    cout << "Element " << eleCount << ": ";
    cin >> x;
    if (x != 1337) {
      a.addNode(x);
    }
    eleCount++;
  }
  cout << "There are " << a.elementAmount() << " elements within the linked list\n";
  cout << "Here they are:\n";
  a.showElements();
  cout << "\nNow would you like to remove an element?: ";
  cin >> response;
  if (response == 'Y') {
    cout << "Which index would you like to remove: ";
    cin >> x;
    a.deleteNode(x);
    a.showElements();
    cout << "There are now " << a.elementAmount() << " elements";
  }
  cout << "\nNow would you like to insert an element?: ";
  cin >> response;
  if (response == 'Y') {
    cout << "Where wouuld you like to insert in an element?: ";
    cin >> x;
    cout << "What value would you like to have for your new element?: ";
    cin >> val;
    a.insertNode(val , x);
    a.showElements();
    cout << "There are now " << a.elementAmount() << " elements";
  }
  cin >> response;
  return (0);
}
jlb (4973)
What is the purpose of all those pointers in your class?

Why do you have to iterate through the whole list just to add an item. One of the purposes of a linked list is to be able to add or remove an element anywhere within the list. Also since you seem to have a tail pointer if you must always delete the last item why not just use the tail pointer to go to that item?

What's with this magic number while(x != 1337), 1337 is a valid integer, why can't I put this number into the list.

I really suggest you do a little more investigation of the purposes of lists, perhaps look at some documentation for the std::list class.

rabster (227)
Well I'm using the pointers for the list. And yeah, now that I think about it this really is a messed up list. I just didn't know how else I would access an index so I just did that. But I'm not sure what you mean about the deleting the last item with the tail pointer? I just have while(x != 1337) so that I can break the loop with that magic number easily. I know its a valid number I just use it to breakout.
Topic archived. No new replies allowed.