C++

Forum

 
Simple linear chained alphabetized lists

TheBane (5)
Hi guys i got a big problem on my head, i missed some weeks of school because of a surgery and now i have to make a project by tomorrow and i have no clue how to do it... google was not helpfull.
It sounds like this:

Write a project, using classes, that performs the merging of two simple linear chained alphabetized lists.


closed account (SECMoG1T)
Willing to help but could you explain what this means linear chained alphabetized lists.  exactly, are they the common std::strings or are they some char linked list or maybe some other object list not sure.
tscott8706 (82)
I would try really hard to request an extension by your teacher. If you don't know how to do it, and it's due by tomorrow, you are most likely going to need more time. If you've had surgery, the professor should hopefully be a little more lenient.
Gamer2015 (810)
I don't understand what a linear chained alphabetized list is ._.

I could help with 2 generic lists :)

You have a List, this list contains of Nodes.
Each Node has a Value and a previous and next node.

when merging 2 of these lists you just have to relink the nodes (eg. set the previous and next node)
TheBane (5)
Sorry not a native english speaker. Well what i ment there is that using classes i have to achive the merging of two simple lists that are alfabetic oraganized. Hope you understand.
fg109 (709)
You would do it like you would in merge sort. Only you don't have to split the lists down to single items first since they're already alphabetically ordered.

http://en.wikipedia.org/wiki/Merge_sort
Last edited on
Gamer2015 (810)
i think you speak german, right?

So, you have a class named List
Do you have to write that class yourself?

Then you make an instance of that List and you insert characters from the alphabet into it.
Then you make a second instance of that List and you insert characters from the alphabet into it.

Then you want to merge those 2 lists, right?
TheBane (5)
Yes i have to write the class myself and merge the 2 lists yea.Phew you got it right gamer:)
Gamer2015 (810)
Then let's begin! :D

first off, you have to decide if you want it to be a single- or double linked list.
In a List you usually have nodes.
These Nodes hold the values
In a single linked list those Nodes also know the next node, the node that comes after them in the list.
In addition to that in a double linked list those Nodes also know the previous one.

Which of them do you need?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
 
template <typename T>
class List
{
public:
    struct Node
    {
        T value;
        Node* next;
        // Node* prev;
    };

public:
    List() : first(nullptr) {}

private:
    Node* first;
};
Last edited on
TheBane (5)
Single linked list
Gamer2015 (810)
So then let's determine how you want the list to work.

You will want to add and delete elements, right?
let's call them...

pop_front, pop_back, push_front, push_back (insert for later)
and of course merge
all these elements return... hm... nothing

well, let's also print it.

And you may want to know if the list has elements or is empty.

In this merge Method, do you want the second list to be modified?
Do you want to be the second list valid after the Lists are merged?

Let's say we have 2 node pointers, one of them marks the beginning and one of them marks the end.
and we have a variable which counts the size
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
140
141
142
143
144
145
 
#include <iostream>

template <typename T>
class List
{
public:
    struct Node
    {
        T value;
        Node* next;
    };

public:
    List() : first(nullptr), last(nullptr), size(0) {}

    bool pop_front()
    {
        if(empty())
            return false;

        Node* second = first->next;
        delete first;
        first = second;

        if(first == nullptr) // if the last element is deleted
            last = nullptr;

        size--;
        return true;
    }
    bool pop_back()
    {
        if(empty())
            return false;

        Node* prev = get_prev(last);
        if(prev != nullptr) // if there was a previous node
            prev->next = nullptr; //set the next of that to be nullptr, to clarify that this node has no next 
            

        delete last;
        last = prev;

        if(last == nullptr) // if the last element is deleted
            first = nullptr;

        size--;
        return true;
    }

    void push_front(T value)
    {
        Node* node = new Node;
        node->value = value;
        node->next = first;
        first = node;

        if(empty()) // if the list was empty the last node is also that node
            last = node;

        size++;
    }
    void push_back(T value)
    {
        Node* node = new Node;
        node->value = value;
        node->next = nullptr; // last node

        if(empty()) // if the list was empty the first node is also that node
            first = node;
        else
            last->next = node; // set the currently last node that the next one is node

        last = node;

        size++;
    }

    void print() const
    {
        std::cout << "size: " << size << std::endl;
        Node* temp = first;
        while(temp != nullptr)
        {
            std::cout << temp->value << std::endl;
            temp = temp->next;
        }
    }

    void merge(const List<T>& list);

private:
    bool empty() const { return size==0; }

    Node* get_prev(const Node* node) const // for nodes in this list to get the previous
    {
        if(node == first || node == nullptr) // if it is the first node
            return nullptr;

        Node* temp = first;
        while(temp != nullptr) // traverse until the end of the list is reached
        {
            if(temp->next == node) // if there is a node that has node as next in this list
                return temp; // return that list
            temp = temp->next;
        }
        return nullptr;
    }

    Node* first;
    Node* last;
    size_t size;
};

int main(void)
{
    List<int> list;

    list.push_back(1);
    list.push_back(2);
    list.push_back(3);
    list.push_front(4);
    list.push_front(5);

    list.print();

    list.pop_back();
    list.pop_front();

    list.print();

    list.pop_back();
    list.pop_front();

    list.print();

    if(list.pop_back() == false)
        std::cout << "list was empty" << std::endl;
    if(list.pop_front() == false)
        std::cout << "list was empty" << std::endl;

    list.print();

    return 0;
}


Note: when popping the success is returned, so if the List was empty it returns false

Is everything clear up to here?
I added a few comments to follow my mind

edit: so, now let's merge them, right? :)
we should make an insert function for that task, but what parameter should it take?
Should you be able to insert after/before a specific node or should you insert your node at a position in the List?
Last edited on
TheBane (5)
Thx , managed to make it with the help of a friend and your info
Gamer2015 (810)
good to hear :)
Topic archived. No new replies allowed.