רשימה

List הוא מכול רצף מובנה בשפת C++ שמאפשר הקצאת זיכרון לא רציפה. כשאנחנו מדברים על list, אנחנו מתכוונים לרשימה מקושרת דו־כיוונית. יש סוג נוסף של רשימה שנקרא forward list, שמשמעותו רשימה מקושרת חד־כיוונית. 

כדי שהכול יהיה ברור. 
מבנה הנתונים vector מאפשר הקצאת זיכרון רציפה, כלומר כל איבר נמצא בזיכרון מיד אחרי האיבר הקודם.
לעומת זאת, למבנה הנתונים linked list יש איברים שמכילים חלק נתונים (הערך עצמו) ומצביע שמכיל את כתובת הזיכרון של האיבר הבא ברשימה.

יש שני סוגים של רשימות מקושרות ב־C++:

• רשימה מקושרת דו־כיוונית - list
• רשימה מקושרת חד־כיוונית - forward list

ההבדל העיקרי בין רשימה מקושרת דו־כיוונית לבין רשימה מקושרת חד־כיוונית הוא שברשימות מקושרות חד־כיווניות אפשר להתקדם רק קדימה, כלומר לכל איבר יש ערך משלו וכתובת הזיכרון של האיבר הבא. לעומת זאת, האיברים ברשימה מקושרת דו־כיוונית שומרים מידע על האופן שבו אפשר לאתר את האיבר הבא ואת האיבר הקודם ברשימה.

אנחנו משתמשים ב־list (רשימה מקושרת דו־כיוונית) וב־forward list (רשימה מקושרת חד־כיוונית) באמצעות הכללתן בקובץ שלנו בעזרת:

#include <list>
#include <forward_list>

לחלופין, פשוט נכלול רק את קובץ הכותרת bits/stdc++.h.

רשימה מקושרת חד־כיוונית

נתחיל בלדבר על forward list. יש לנו שיטות רבות עבור רשימה מקושרת חד־כיוונית, ונדבר על השימושיות ביותר.
אנחנו מצהירים על forward list בדיוק כפי שעשינו עם vector ו־deque.

forward_list<int> flist = {1, 2, 3};

אפשר להוסיף איברים באמצעות השיטה push_front() ולהסיר איברים מההתחלה באמצעות pop_front().

flist.push_front(5);
for (int &x : flist) // אנו מדפיסים את האיברים באמצעות מצביע שערכו גדל בכל איטרציה
	cout << x << " ";
cout << endl;

flist.pop_front();
for (int &x : flist)
	cout << x << " ";

Output:
5 1 2 3
1 2 3

שיטות של רשימה מקושרת חד־כיוונית

רשימה מקושרת דו־כיוונית

הבא בתור הוא list. יש גם שיטות רבות שאפשר להשתמש בהן עם מבנה הנתונים list, אבל נכיר את השימושיות ביותר. 
תחילה נלמד איך להצהיר על list אחרי הכללתו בראש קובץ ה־.cpp. 

list<int> list1 = {1, 2, 3};

אפשר להוסיף איברים לרשימה באמצעות השיטה push_front() או push_back().
בדומה לכך, אפשר להסיר את האיבר הראשון והאחרון באמצעות השיטות pop_front() ו־pop_back(), בהתאמה.

list1.push_back(4);
list1.push_front(0);
for (int &x : list1)
	cout << x << " ";
cout << endl;

list1.pop_front();
list1.pop_back();
for (int &x : list1)
	cout << x << " ";

Output:
0 1 2 3 4
1 2 3

שיטות של רשימה מקושרת דו־כיוונית