[STL] list #1

list (연결 리스트)

• list의 동작 원리
• 중간 삽입/삭제
• 처음/끝, 삽입/삭제
• 임의 접근 (Random Access)

 

list<int> li;

for (int i = 0; i < 100; ++i)
‌li.push_back(i);

li.push_front(0);     // vector는 처음 삽입이 비효율적이라 없음

int size = li.size();
//li.capacity();  // 없음

int first = li.front();
int last = li.back();

// li[3] = 10    // 임의접근 허용안됨

list<int>::iterator itBegin = li.begin();
list<int>::iterator itEnd = li.end();

li.insert(itBegin, 100);

li.erase(li.begin());

li.pop_front();

li.remove(10);     // val와 같은 데이터인 원소는 모두 다 삭제. vector는 비효율적이라 없음.

 

단일 : [1] → [2] → [3] → [4] → [5]

이중 : [1] ←→ [2] ←→ [3] ←→ [4] ←→ [5]

원형 : [1] ←→ [2] ←→ [3] ←→ [4] ←→ [5] ←→

// Node [ data(4) next(4/8) ] -> Node [ data(4) next(4/8) ]
class Node
{
​​​​public:
​​​​​​​​Node* _next;
​​​​​​​​int _data;
}