연결리스트

연결리스트란 무엇인가?

-원소들을 저장할때 그다음 원소가 있는 위치를 포함시키는 방식으로 저장하는 자료구조

 

연결리스트의 성질은?

1. K번째 원소를 확인/변경하기 위해 O(K)가 소요됨
2. 임의의 위치에 원소를 추가/제거는 O(1)
3. 원소들이 메모리상에 연속해 있지 않아 Cache hit rate가 낮지만 할당이 쉬움
4. 추가적으로 필요한 공간(Overhead)가 O(n)이 필요(주소값)

연결리스트의 종류

1. 단일 연결 리스트
2. 이중 연결 리스트
3. 원형 연결 리스트

연결리스트의 용도는?

1. 임의의 위치에서 원소를 추가/삭제가 빈번할때(ex. 메모장)
2. 커서 이동이 빈번할때

 

STL

list<int> L = {1,2};
list<int> auto t = L.begin();
L.push_front(10); // 10 1 2
cout << *t << '\n'; // 1
L.push_back(5); // 10 1 2 5
L.insert(t,6); // 10 6 1 2 5
t++; // t는 2를 가리킴
t = L.erase(t);// 2삭제후 5의 주소를 리턴
cout << *t << '\n'; // 5
for(auto i : L) cout << i << ' ';
cout << '\n';
for(list<int>:: iterator it = L.begin(); it != L.end(); it++)
	cout << i << ' '; // C+11버전 미만