সি/সি++ এ আমারা যখন কোনো টাইপের ভ্যারিয়েবল ডিক্লেয়ার করি তখন ঐ টাইপের জন্য মেমরি অ্যালোকেট হয়। এটাকে সম্ভবত স্ট্যাটিক মেমরি অ্যালোকেশন বলা হয়। আমরা কি স্ট্যাটিক মেমরি অ্যালোকেট করে লিঙ্কড লিস্ট ইমপ্লিমেন্ট করতে পারি না?

test1.cpp

#include <bits/stdc++.h>
using namespace std;

struct test
{
    int data;
    test *next;
};

int main()
{
    test a, b, c, d;
    a.data = 10;
    b.data = 20;
    c.data = 30;
    d.data = 40;
    a.next = &b;
    b.next = &c;
    c.next = &d;
    d.next = NULL;
    test *p;
    p = &a;
    while(p->next != NULL){
        cout << p->data << " ";
        p = p->next;
    }
    cout << p->data << "\n";
    return 0;
}

উপরের কোড (test1.cpp) রান করে ঠিকঠাক আউটপুট পাচ্ছি। কিন্তু নিচের কোড (test2.cpp) চালিয়ে সঠিক আউটপুট পাচ্ছি না কেন?

test2.cpp

#include <bits/stdc++.h>
using namespace std;

struct test
{
    int data;
    test *next;
};

void create(test *mylist)
{
    cin >> mylist->data;
    if(mylist->data == -100000){
        mylist->next = NULL;
        return;
    }
    test neww;
    mylist->next = &neww;
    create(&neww);
}
void printList(test *head)
{
    while(head->next != NULL){
        cout << head->data << " ";
        head = head->next;
    }
    cout << head->data << "\n";
}
int main()
{
    test head;
    create(&head);
    printList(&head);
    return 0;
}

বিঃ দ্রঃ test2.cpp এর ইনপুট শেষ করতে শেষে -100000 ইনপুট দিন।

asked 06 Apr, 05:34

imTroy's gravatar image

imTroy
17312

edited 09 Apr, 01:27


লিঙ্ক লিস্ট বানানোর সময় একটা বিষয় আপনাকে মনে রাখতে হবে সেটা হল । আপনাকে head node এর ইনফরমেশন নষ্ট করা যাবে না । আপনার test2.cpp তে head node এর পয়েন্টের প্রতিবার আপডেট হচ্ছে। যার কারণে সমস্যা হচ্ছে। আপনি এই ভাবে লিঙ্ক লিস্ট ইমপ্লিমেন্ট করতে পারেন।

#include <bits/stdc++.h>
using namespace std;

struct test
{
    int data;
    test *next;
};

test *head = NULL;

void create()
{
    int a;
    cin >> a;
    cout << "a" << a << endl;
    if(a == -1){
        return;
    }
    // create a node
    test *new_node = new test();
    new_node->data = a;
    new_node->next = NULL;

    // check head is null or not
    if(head == NULL) {
        head = new_node;
    }
    else {
        // if head is not NULL then iterate to
        // end of head
        test *tmp = head;
        while(tmp->next != NULL) {
            tmp = tmp->next;
        }
        // assign new node to head's end
        tmp->next = new_node;
    }
    create();
}
void printList()
{
    while(head->next != NULL){
        cout << head->data << endl;
        head = head->next;
    }
    cout << head->data << "\n";
}
int main()
{
    create();
    printList();

    return 0;


}

ধন্যবাদ :)

permanent link

answered 06 Apr, 17:11

menon's gravatar image

menon
4.4k328

edited 07 Apr, 08:26

Mosharraf%20Hosain's gravatar image

Mosharraf Hosain ♦
48618

1

হেড নোড কিভাবে প্রতিবার আপডেট হচ্ছে এটা কি ব্যাখ্যা করা যাবে? আমি বুঝতে পারছি না।

(06 Apr, 22:38) Ashfaqur Rahman
1

প্রথমেই ধন্যবাদ আপনাকে। head node এর ইনফরমেশন কিভাবে নষ্ট হচ্ছে বুঝি নি? head node ত প্রতিবার update করছি না। create function কলের আগে এবং create function কলের পরে আপনি head এর address print করে দেখতে পারেন। আর আপনার solution এ create function এর complexity ত বেড়ে গেল মনে হচ্ছে।

(07 Apr, 02:43) imTroy

@Ashfaqur Rahman, @imTroy হুম আপনারা ঠিক ধরেছেন । head node এর ইনফরমেশন আসলে নষ্ট হচ্ছে না । আমার কাছে মনে হচ্ছে একটার সাথে অন্য একটা node এর লিঙ্ক হচ্ছে না । কেন হচ্ছে না এই বিষয়টা আমিও বুঝতে পারছি না । বিষয়টা বোঝার জন্য আমি প্রিন্ট ফাংশন টা এই ভাবে লিখেছিলাম,

void printList(test *head)
{
    cout << "print list:" << endl;
    while(head->next != NULL){
        cout << "head: " << head << endl;
        cout << head->data << "\n";
        head = head->next;
    }
    cout << head->data << "\n";
} 

এবং দেখতে পেলাম যে head তার নেক্সট পয়েন্টের টা খুজে পাচ্ছে না ।

(07 Apr, 07:52) menon
1

আমি নিজে যখন টেস্ট করেছিলাম তখন প্রিন্ট দিয়ে দেখেছিলাম হেডনোড ঠিক থাকে। সে পরবর্তী নোডটাও খুঁজে পায় কিন্তু এরপরের নোডগুলোর আর লিঙ্ক থাকে না।

এটা থেকে ধারনা করেছিলাম সমস্যাটা হতে পারে লোকাল ভ্যারিয়েবলের জন্য। কারণ হেড নোড বাদে পরবর্তী সব নোডগুলোই তৈরি হচ্ছে ফাংশনের ভেতর। যেকারণে ফাংশন কল করলেই নোডগুলো তৈরি হচ্ছে আর ফাংশন রিটার্ন করলেই ধ্বংস হয়ে যাচ্ছে।

যেহেতু হেড নোড মেইন ফাংশে তৈরি সেহেতু এটা ঠিক থাকছে এবং একটা নোডের ইনফর্মেশন সে তার নেক্সট পয়েন্টারে রাখতে পারছে, যেকারণে সেটা খুঁজে পাওয়া যায়।আর পরবর্তী নোডটা লোকাল,কল করার সাথে তৈরি হয়ে ধ্বংস হয়ে যাচ্ছে,তাই এর থেকে আর কোন লিঙ্ক পাওয়া যায় না।

(09 Apr, 04:33) Ashfaqur Rahman

নিশ্চিত ছিলাম না তাই তখন উত্তর দেই নি। এখন মনে হয় দেয়া যেতে পারে!

@menon

(09 Apr, 04:34) Ashfaqur Rahman

লিস্ট তৈরি হয়ে যাওয়ার পর পয়েন্টারগুলো প্রিন্ট করলে দেখা যাবে লিস্টে শুধুমাত্র হেড নোড এবং তার পরবর্তী নোডটা খুঁজে পাওয়া যায় আর কোন নোড পাওয়া যায় না। পয়েন্টারগুলো প্রিন্ট করা যাবে এভাবে:

void printList(test *head)
{
    cout << "print list:" << endl;
    while(head->next != NULL){
        cout << "head: " << head << endl;
        cout << head->data << "\n";
        head = head->next;
    }
    cout << head->data << "\n";
}

(কার্টেসি: @menon)

সম্ভবত সমস্যাটা হচ্ছে লোকাল ভ্যারিয়েবলের জন্য। কারণ হেড নোড বাদে পরবর্তী সব নোডগুলোই তৈরি হচ্ছে ফাংশনের ভেতর। সেগুলো ফাংশনের লোকাল ভ্যারিয়েবল। যেকারণে ফাংশন কল করলেই নোডগুলো তৈরি হচ্ছে আর ফাংশন রিটার্ন করলেই ধ্বংস হয়ে যাচ্ছে।

যেহেতু হেড নোড মেইন ফাংশে তৈরি সেহেতু এটা ঠিক থাকছে এবং একটা নোডের ইনফর্মেশন সে তার নেক্সট পয়েন্টারে রাখতে পারছে, যেকারণে সেটাও খুঁজে পাওয়া যায়। আর এই পরবর্তী নোডটা লোকাল, যেকারণে ফাংশন কল করার সাথে সাথেই তৈরি হয়ে ধ্বংস হয়ে যাচ্ছে, তাই এরপর থেকে আর কোন লিঙ্ক পাওয়া যায় না। আবার যেহেতু ভ্যারিয়েবল গুলো যে মেমরি নিচ্ছে তা হচ্ছে ফাংশনের স্ট্যাক মেমরি একারণে ফাংশন কল শেষ হওয়ার পর পয়েন্টার দিয়েও সে মেমরিতে একসেস করা যাচ্ছে না।

তাই প্রিন্ট করতে গেলে শুধু পাওয়া যাচ্ছে head এবং head->next। মানে শুধুমাত্র হেড নোডটিই।

ডায়ানামিক্যালি মেমরি অ্যালোকেট করে নিলে এই সমস্যাটা হয় না যেহেতু সেক্ষেত্রে মেমরি নেয়া হয় হিপ থেকে। যেটা সব সময়ই এভেইলেবল।

permanent link

answered 09 Apr, 04:56

Ashfaqur%20Rahman's gravatar image

Ashfaqur Rahman
7839

edited 09 Apr, 10:04

Your answer
toggle preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported

Question tags:

×4
×4
×3

question asked: 06 Apr, 05:34

question was seen: 135 times

last updated: 09 Apr, 10:04