-
1. 노드 접근 방법
원하는 위치로 바로 갈 수 있는 것이 아니다.
head에서 시작해 해당 노드까지 하나씩 읽어 나가는 방식이다.
즉, 원하는 노드가 tail이라면 총 n번의 시간이 소요되는 셈인 것이다.
삽입과 삭제 자체만 보았을 때 O(1)이 걸려도, 찾는 것이 O(n)이 걸려 최종적이로 O(n)이 된다는 특징이 있다.
2. 종류
- Singly Linked List
- Doubly Linked List
- Circular Linked List
3. Simply Linked List(단일 연결 리스트)
(1) 삽입
- head로 삽입
: O(1)
- tail로 삽입
: O(1)
- 중간 node로 삽입
: O(n)
(2) 삭제
- head 삭제
: O(1)
- tail 삭제
: O(n)
- 중간 node 삭제
: O(n)
4. Doubly Linked List(이중 연결 리스트)
(1) 삽입
: O(n)
(2) 삭제
: O(n)
5. Circular Linked List(환형 연결 리스트)
(1) 삽입
: O(n)
(2) 삭제
: O(n)
6. 실제 활용 코드(단일 연결 리스트 활용) : 백준 1406 에디터
#include<iostream> #include<list> using namespace std; int main() { list<char> mylist; //전체 node list<char>::iterator it; //cur node string str; cin >> str; for (int i = 0; i < str.size(); i++) { mylist.push_back(str[i]); } it = mylist.end(); int order; cin >> order; for (int i = 0; i < order; i++) { char type; cin >> type; switch (type) { case 'L': if(it!=mylist.begin()) it--; break; case 'D': if (it != mylist.end()) it++; break; case 'B': if (it != mylist.begin()) { it--; it = mylist.erase(it); } break; case 'P': char c; cin >> c; mylist.insert(it, c); break; }//switch end }//for end for (it = mylist.begin(); it != mylist.end(); it++) { cout << *it; } return 0; }
⚠️ 주의점: list의 erase의 기능 사용 ⚠️
: insert와 달리, erase는 해당 노드를 삭제하게 되면 노드의 next 주소를 잃어버리게 된다.
mylist.erase(it);
그렇기에 위와 같이 사용하게 된다면, 런타임 에러가 발생하게 된다.
고로 다음 노드의 주소를 알려줘야 한다.
erase의 return값은 삭제한 노드의 다음 노드 값이기에, 다음과 같이 it을 업데이트 해주면 오류는 사라진다.
it=mylist.erase(it);
7. 실제 코드 활용 주소
'프로그래밍 > C++' 카테고리의 다른 글
[알고리즘/백준] 아스키코드 (0) 2022.07.31 [알고리즘/백준] 소수 판별 (0) 2022.07.20 [알고리즘/백준] 재귀함수 (0) 2022.07.19 쓰레드(thread) (0) 2022.01.15 [진수 변환] 16진수/10진수/8진수 입출력 변환 (0) 2021.08.29 [프로그래머스] 더 맵게 / 힙 / C++ / 문제 풀이 🔍 (0) 2021.06.28 [C++] STL Priority Queue(우선순위 큐) 활용법 (0) 2021.06.28 [C++] STL Dequeue 활용법 (0) 2021.06.28 댓글