list: node-এর একটা শিকল, যেটা যেকোনো জায়গায় কেটে আবার জোড়া যায়

Maria ওর playlist রাখে একটা vector-এ, আর এখন কোন গান বাজছে সেটা মনে রাখে index দিয়ে। আজ ও চায় একটা নতুন গান ঠিক এখনকার গানটার আগে ঢোকাতে, আরেকটা ঠিক পরে। দুটোই এক লাইনের code। কিন্তু একটার খরচ ও যা ভাবছে তার চেয়ে বেশি, আর অন্যটা চুপচাপ ওর index-টাই নষ্ট করে দেয়। এই lesson ওকে এমন একটা container দেবে, যেখানে একটা position যেখানে ছিল সেখানেই থাকে: std::list।

Vector-এ playlist রাখলে দুইটা সমস্যা

এই হলো Maria-র প্রথম চেষ্টা। এখন বাজছে 2 নম্বর গান, আর ও একটা নতুন গান insert করে index 1-এ, মানে বাজতে থাকা গানের সামনে।

#include <iostream>
#include <string>
#include <vector>
using namespace std;

int main() {
    vector<string> playlist{"Intro", "Rain", "Train", "Outro"};
    size_t now = 2;
    cout << "now playing: " << playlist[now] << '\n';
    playlist.insert(playlist.begin() + 1, "Storm");
    cout << "after an insert in front of it: " << playlist[now] << '\n';
    return 0;
}

now playing: Train
after an insert in front of it: Rain

কিছুই crash করেনি, অথচ উত্তরটা ভুল। Insert-টা "Train"-কে index 2 থেকে ঠেলে index 3-এ পাঠিয়ে দিয়েছে, তাই রাখা index এখন বলছে "Rain"। Index মানে "তিন নম্বর বাক্স", "এই গানটা" না, আর বাক্সের নম্বর বদলে যায়। এটাই প্রথম সমস্যা: যে position তুমি মনে রেখেছিলে, সেটা তোমার অজান্তেই সরে যেতে পারে।

দ্বিতীয় সমস্যা খরচ। Vector-এর মাঝখানে একটা insert পরের প্রতিটা element-কে এক বাক্স ডানে সরায়। Module 2-এর lesson 02 সবচেয়ে খারাপ অবস্থাটা মেপেছিল: vector-এর সামনে 100,000টা insert-এ লেগেছিল প্রায় এক সেকেন্ডের তিন ভাগের এক ভাগ। লম্বা playlist হলে প্রতিটা insert-এ এই সরানোর দাম দিতে হয়।

সমাধানটা তুমি আগেই দেখেছ। C Module 14-এর lesson 04-এ তুমি হাতে একটা linked list বানিয়েছিলে। ওটা ছিল একটা value আর একটা next pointer-ওয়ালা struct node, প্রতিটা node-এর জন্য একটা malloc, আর একটা push_front, যেটা শুধু একটা pointer নতুন করে জুড়ত। Node যোগ করার সময় কিছুই নড়েনি। std::list সেই একই ধারণা, শুধু প্রতিটা node-এ আরেকটা link বেশি, আর malloc, link জোড়া, free সব একবারই লেখা আছে library-র ভিতরে। তাই list প্রতিটা value-কে যেখানে প্রথম রেখেছিল সেখানেই রাখে, বদলায় শুধু link।

ছবিটা: দুইটা link-ওয়ালা একটা node

Node মানে heap-এর উপর একটা ছোট block, যেটা একটা value আর দুইটা link রাখে। next রাখে পরের node-এর address, আর prev রাখে আগের node-এর address। আর list object-টা নিজে, মানে যে l তুমি declare করো, সে রাখে প্রথম node, শেষ node আর একটা গুনতি। Value-গুলো ও কখনো পাশাপাশি রাখে না।

আসল তফাতটা ওই দ্বিতীয় link-এ। prev থাকায় একটা node দুই পাশের প্রতিবেশীকেই চেনে, তাই পেছনের দিকে হাঁটা যায়, আর আগের node খুঁজে বের না করেই একটা node erase করা যায়। GCC 12-এ একটা int-এর node heap-এর কাছে চায় 24 byte: 8 byte করে দুইটা link, 4 byte-এর value আর 4 byte padding। এটা মেপে দেখাবে lesson 05। তাই একটা value মানে একটা node, আর list object শুধু দুই মাথা আর গুনতিটা রাখে।

এবার নড়াচড়াটা দেখো। নিচের প্রতিটা ধাপ একই list-এর উপর একটা করে call। খেয়াল করো কোন node-গুলোর link বদলায়, erase হলে কোনটা ঝাপসা হয়ে যায়, আর node 30-কে, যেটা আসার পরে আর কেউ ছোঁয় না।

ওই ছয় ধাপে কী কী সরল, গুনে দেখো: কিছুই না। প্রতিটা node যে address-এ জন্মেছিল সেখানেই রয়ে গেছে, আর প্রতিটা call বড়জোর চারটা link বদলেছে। তাই position হাতে থাকলে list-এ একটা insert বা erase যেখানেই হোক, খরচ সেই অল্প কয়েকটা ধাপই।

প্রথম দিনেই যে syntax লাগবে

#include <list>

list<T> l;                    an empty list of T
l.push_back(x);               add x after the last element
l.push_front(x);              add x before the first element
l.pop_back();                 remove the last element
l.pop_front();                remove the first element
l.front()   l.back()          the first and the last element
l.size()    l.empty()         how many, and whether there are none
l.begin()   l.end()           an iterator to the first, and to past the last
++it;  --it;  *it             step forward, step back, read the element
l.insert(it, x)               add x before it; returns the new node's iterator
l.erase(it)                   remove the element at it; returns the next one
l.splice(pos, other)          move every node of other in before pos

তাই list-এর দুই মাথাতেই একটা করে push আর pop আছে, আর মাঝখানের সব কাজ হয় একটা iterator দিয়ে।

Index নেই: হাঁটতে হয় ++ আর -- দিয়ে

Vector v[2] খুঁজে পায় একটা যোগ দিয়ে: প্রথম বাক্স যোগ দুই বাক্স। List-এর এমন কোনো যোগ নেই, কারণ ওর node-গুলো heap যেখানে জায়গা দিয়েছে সেখানে ছড়িয়ে আছে। তাই ওর operator[]-ই নেই। Bob তবুও চেষ্টা করে।

list<int> l{10, 20, 30};
cout << l[1] << '\n';

GCC 12 থেমে যায় এই বলে: error: no match for 'operator[]' (operand types are 'std::__cxx11::list<int>' and 'int')। নামের ভিতরের __cxx11 আর কিছু না, GCC-র library নিজের list-এর version-টাকে এভাবে চিহ্ন দেয়। দ্বিতীয় element-এ পৌঁছাতে হলে শুরু করো begin() থেকে, আর একটা link ধরে এগোও।

#include <iostream>
#include <list>
using namespace std;

int main() {
    list<int> l{10, 20, 30, 40};

    cout << "forward:";
    for (list<int>::iterator it = l.begin(); it != l.end(); ++it) {
        cout << ' ' << *it;
    }

    cout << "\nbackward:";
    list<int>::iterator it = l.end();
    while (it != l.begin()) {
        --it;
        cout << ' ' << *it;
    }

    it = l.begin();
    ++it;
    ++it;
    cout << "\nthe third one: " << *it << '\n';
    return 0;
}

forward: 10 20 30 40
backward: 40 30 20 10
the third one: 30

পেছনের দিকের হাঁটা শুরু হয় end() থেকে, মানে শেষ element-এর পরের জায়গা থেকে, আর পড়ার আগে এক পা পিছায়। এই ক্রমটা জরুরি: *l.end() কোনো element না। Range-for, মানে for (int x : l), সামনের দিকের হাঁটাটা তোমার হয়ে করে দেয়, আর পুরো list পড়ার চেনা উপায় এটাই। তাই k নম্বর element-এ পৌঁছাতে k ধাপ লাগে, আর list পড়া হয় এক মাথা থেকে বা অন্য মাথা থেকে।

insert নতুন node বসায় iterator-এর আগে

l.insert(it, x) x-এর জন্য একটা নতুন node বানায়, আর it যে node-কে দেখাচ্ছে, তার ঠিক আগে জুড়ে দেয়। নিচের ছবিটা widget-এর পাঁচ নম্বর ধাপ, ধীরে চালানো।

Call-টা নতুন node-এর একটা iterator return করে, আর পুরোনো iterator-এ হাতই পড়ে না। l.insert(l.end(), x) আর push_back একই কথা, আর l.insert(l.begin(), x) আর push_front একই কথা।

#include <iostream>
#include <list>
using namespace std;

int main() {
    list<int> l{10, 20, 30};
    list<int>::iterator it = l.begin();
    ++it;
    list<int>::iterator fresh = l.insert(it, 15);
    cout << "fresh: " << *fresh << ", it: " << *it << '\n';

    l.insert(l.end(), 40);
    l.insert(l.begin(), 5);
    cout << "list:";
    for (int x : l) {
        cout << ' ' << x;
    }
    cout << '\n';
    return 0;
}

fresh: 15, it: 20
list: 5 10 15 20 30 40

তাই insert সবসময় বসে তোমার দেওয়া iterator-এর সামনে, আর iterator-টা একই element-কে দেখাতে থাকে।

erase, আর it = l.erase(it) দিয়ে হাঁটা

l.erase(it) it-এর দুই প্রতিবেশীকে একে অন্যের সাথে জুড়ে দেয়, আর ওর node-টা free করে দেয়। এরপর it দেখায় free হয়ে যাওয়া memory, ওটা আর ব্যবহার করা চলবে না। এজন্যই erase পরের node-এর একটা iterator return করে: তোমার হাঁটা চলবে ওখান থেকেই।

Zara-র sensor কোনো reading ফসকালে 0 লেখে। ও list-টা একবার হেঁটে প্রতিটা 0 erase করে দেয়।

#include <iostream>
#include <list>
using namespace std;

int main() {
    list<int> readings{21, 0, 23, 0, 0, 24};

    list<int>::iterator it = readings.begin();
    while (it != readings.end()) {
        if (*it == 0) {
            it = readings.erase(it);
        } else {
            ++it;
        }
    }

    cout << "readings:";
    for (int r : readings) {
        cout << ' ' << r;
    }
    cout << " (size " << readings.size() << ")\n";
    return 0;
}

readings: 21 23 24 (size 3)

পরপর দুইটা শূন্যের দিকে তাকাও। প্রথমটা erase হওয়ার পরে it এরই মধ্যে দ্বিতীয়টাকে দেখাচ্ছে, তাই loop-কে আর আলাদা করে এক পা এগোলে চলবে না। এজন্যই ++it বসেছে else-এর ভিতরে। এই পুরো হাঁটাটা এক call-এ করে দেয় remove, সেটা দেখাবে lesson 02। তাই যে হাঁটায় erase আছে, সেটা একটা while loop, আর সেখানে এগোনো হয় হয় erase দিয়ে, নয়তো ++it দিয়ে, কখনো দুটো একসাথে না।

যে position টিকে থাকে

Widget যে কথা দিয়েছিল, এই সেটা। Insert কখনো আগের কোনো node সরায় না, আর erase শুধু নিজের node-টা free করে। তাই অন্য যেকোনো element-এর iterator ঠিক থাকে: ওটা এখনো একই node দেখায়, একই value সমেত। এই program widget-এর ছয়টা call আবার চালায়, আর পুরো সময় দুইটা iterator ধরে রাখে।

#include <iostream>
#include <list>
#include <string>
using namespace std;

void show(const string& call, const list<int>& l) {
    cout << call << ":";
    for (int x : l) {
        cout << ' ' << x;
    }
    cout << '\n';
}

int main() {
    list<int> l;
    l.push_back(10);
    l.push_back(20);
    l.push_back(30);
    list<int>::iterator thirty = l.end();
    --thirty;
    list<int>::iterator twenty = thirty;
    --twenty;
    show("three push_back", l);

    l.push_front(5);
    show("push_front(5)", l);
    list<int>::iterator fifteen = l.insert(twenty, 15);
    show("insert 15 before 20", l);
    l.erase(twenty);
    show("erase 20", l);

    cout << "fifteen points at " << *fifteen << ", thirty at " << *thirty << '\n';
    return 0;
}

three push_back: 10 20 30
push_front(5): 5 10 20 30
insert 15 before 20: 5 10 15 20 30
erase 20: 5 10 15 30
fifteen points at 15, thirty at 30

thirty বানানো হয়েছিল আরও চারটা call list-টা বদলানোর আগে, আর ও এখনো 30-ই পড়ে। মারা গেছে শুধু twenty, ওর node-এর সাথে, আর program ওকে আর কখনো ছোঁয় না। Vector এমন কোনো কথা দেয় না: একটা insert reallocate করে সব element সরিয়ে ফেলতে পারে, Module 2-এ যেমন দেখেছ। তাই list-এ একটা erase শুধু erase হওয়া element-এর iterator-টাই নষ্ট করে, আর insert কোনোটাই না।

splice: অন্য list থেকে node নিয়ে আসা

List এমন একটা কাজ পারে, যেটা এই track-এর আর কোনো container পারে না। l.splice(pos, other) other-এর সব node বের করে এনে l-এ pos-এর আগে জুড়ে দেয়। কোনো value copy হয় না, কোনো node নতুন করে বানানো বা free হয় না: বদলায় শুধু দুই জোড়ের জায়গার link। দেখো, দেরিতে আসা তিনটা পাতা কীভাবে একটা report-এ ঢুকে যায়।

নিচের program ঠিক এই splice-টাই করে, আর check করে দেখে 3 রাখা node-টা আগের সেই node-ই কি না।

#include <iostream>
#include <list>
using namespace std;

int main() {
    list<int> pages{1, 2, 6};
    list<int> late{3, 4, 5};
    list<int>::iterator three = late.begin();
    const int* where = &*three;

    list<int>::iterator pos = pages.end();
    --pos;
    pages.splice(pos, late);

    cout << "pages:";
    for (int p : pages) {
        cout << ' ' << p;
    }
    cout << "\nlate holds " << late.size() << " pages\n";
    cout << "three: " << *three << ", same node: " << (where == &*three) << '\n';
    return 0;
}

pages: 1 2 3 4 5 6
late holds 0 pages
three: 3, same node: 1

&*three হলো three যে value-কে দেখায়, তার address। আগে-পরে দুইবারই এটা একই, তাই node-টা সত্যিই memory-তে না সরেই এক list থেকে আরেক list-এ গেছে। Iterator three এখনো ঠিক আছে; ও এখন হাঁটে pages-এর ভিতরে। তাই splice পুরো একটা list সরিয়ে ফেলে কয়েকটা link লিখেই, ওতে যত node-ই থাকুক, আর ওর বাকি দুইটা রূপ দেখাবে lesson 02।

forward_list: একমুখী ভাই

std::forward_list হুবহু সেই list, যেটা তুমি C-তে বানিয়েছিলে: প্রতিটা node-এ একটা value আর next, আর কিছু না। ওর থাকার জায়গা <forward_list>। একটাই link থাকায় একটা node ওর আগের node-এ পৌঁছাতে পারে না। তাই কোনো position-এর আগে insert নেই: আছে insert_after, যেটা তোমার হাতের node-এর পরে একটা node জোড়ে।

#include <forward_list>
#include <iostream>
#include <list>
using namespace std;

int main() {
    forward_list<int> f;
    f.push_front(30);
    f.push_front(10);
    forward_list<int>::iterator it = f.begin();
    f.insert_after(it, 20);

    cout << "f:";
    for (int x : f) {
        cout << ' ' << x;
    }
    cout << '\n';
    cout << "sizeof(forward_list<int>): " << sizeof(forward_list<int>) << '\n';
    cout << "sizeof(list<int>): " << sizeof(list<int>) << '\n';
    return 0;
}

f: 10 20 30
sizeof(forward_list<int>): 8
sizeof(list<int>): 24

একটা forward_list object মাত্র একটা pointer, 8 byte, যেখানে list-এর লাগে 24। ওর size() নেই, push_back নেই, --it-ও নেই। প্রতিটা না-থাকা call GCC 12-এর বার্তাসহ, আর ওর বাকি operation-গুলো, দেখাবে lesson 02। তাই forward_list নাও শুধু তখন, যখন একমুখী হাঁটাই যথেষ্ট আর প্রতিটা byte-এর হিসাব আছে।

#include <iostream>
#include <list>
using namespace std;

int main() {
    list<int> l{20, 30};
    l.push_front(10);
    l.push_back(40);
    cout << "front " << l.front() << ", back " << l.back() << ", size " << l.size() << '\n';
    l.pop_front();
    l.pop_back();
    cout << "front " << l.front() << ", back " << l.back() << ", size " << l.size() << '\n';
    return 0;
}

front 10, back 40, size 4
front 20, back 30, size 2

#include <iostream>
#include <list>
#include <string>
using namespace std;

int main() {
    list<string> train{"engine", "coach A", "coach B"};

    list<string>::iterator it = train.begin();
    ++it;
    train.insert(it, "dining car");
    train.push_back("guard van");

    for (it = train.begin(); it != train.end(); ++it) {
        if (*it == "coach B") {
            train.erase(it);
            break;
        }
    }

    bool first = true;
    for (const string& car : train) {
        cout << (first ? "" : " - ") << car;
        first = false;
    }
    cout << '\n';
    return 0;
}

engine - dining car - coach A - guard van

#include <iostream>
#include <list>
#include <string>
using namespace std;

int main() {
    list<string> playlist{"Intro", "Rain", "Train", "Outro"};
    list<string>::iterator now = playlist.begin();
    ++now;
    ++now;
    const string* where = &*now;
    cout << "now playing: " << *now << '\n';

    list<string>::iterator second = playlist.begin();
    ++second;
    playlist.insert(second, "Storm");

    list<string>::iterator after = now;
    ++after;
    playlist.insert(after, "Snow");

    playlist.erase(playlist.begin());

    cout << "now playing: " << *now << '\n';
    cout << "same node: " << (where == &*now) << '\n';
    cout << "playlist:";
    for (const string& song : playlist) {
        cout << ' ' << song;
    }
    cout << '\n';
    return 0;
}

now playing: Train
now playing: Train
same node: 1
playlist: Storm Rain Train Snow Outro

list<int> l{10, 20, 30};
list<int>::iterator it = l.begin();
cout << *(it + 1) << '\n';

list<int> l{1, 0, 2};
for (list<int>::iterator it = l.begin(); it != l.end(); ++it) {
    if (*it == 0) {
        l.erase(it);
    }
}

#include <iostream>
using namespace std;

int main() {
    list<int> l{10, 20};
    cout << l.size() << '\n';
    return 0;
}

list<int> l{10, 20, 30};
l.insert(1, 15);

#include <iostream>
#include <list>
using namespace std;

int main() {
    list<int> l{1, 2, 3};
    int passes = 0;
    for (list<int>::iterator it = l.begin(); it != l.end(); ++it) {
        l.insert(it, *it * 10);
        passes++;
    }
    cout << "passes: " << passes << '\n';
    for (int x : l) {
        cout << x << ' ';
    }
    cout << '\n';
    return 0;
}

#include <iostream>
#include <list>
using namespace std;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n = 0;
    cin >> n;
    list<int> tasks;
    for (int i = 0; i < n; i++) {
        int x = 0;
        cin >> x;
        tasks.push_back(x);
    }

    // Walk tasks once with an iterator: erase every negative number,
    // and insert a copy right after every even one that stays.

    // Print tasks on one line, or the word empty if nothing is left.

    return 0;
}

#include <iostream>
#include <list>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;
    list<int> row;
    for (int i = 0; i < n; i++) {
        int x;
        cin >> x;
        row.push_back(x);
    }

    // Walk one iterator forward from row.begin() and one backward
    // from row.end(), n / 2 steps each, comparing the two values.
    // Print yes if every pair matched, otherwise no.

    return 0;
}

#include <iostream>
#include <list>
using namespace std;

int main() {
    int n, t;
    cin >> n >> t;
    list<int> deck;
    for (int c = 1; c <= n; c++) {
        deck.push_back(c);
    }

    // Repeat t times: move the bottom half of deck into its own list,
    // then put its cards back one by one, each after a card of the top
    // half. Then print deck from top to bottom.

    return 0;
}

এরপর lesson 02 list আর forward_list-এর প্রতিটা operation একটা একটা করে দেখাবে, প্রতিটার খরচসহ।