[자료구조 복습] Linked List

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. 실제 코드 활용 주소

⛏️ 본인의 깃허브

GitHub - minjeongss/Algorithm: 알고리즘 문제 풀이 Repository 🚀