[Algorithm] 연결리스트(Linked List)

연결리스트(Linked List)

 

-정의: 각 노드가 데이터와 포인터를 가지고 한 줄로 연결되어 있는 방식으로 데이터를 저장하는 자료 구조이다. 이름에서 말하듯이 데이터를 담고 있는 노드들이 연결되어 있는데, 노드의 포인터가 다음이나 이전의 노드와의 연결을 담당한다.

 

-특징

    (1) 원소들은 메모리 상에 불연속적으로 위치하고 있어도 무방

 

-종류

    (1) 단일 연결리스트(Singly Linked List)

단일 연결리스트(Singly Linked List)

        -정의: 각 노드에 자료 공간과 한 개의 포인터 공간이 있고, 각 노드의 포인터는 다음 노드를 가리킴

 

    (2) 이중 연결리스트(Doubly LInked List)

이중 연결리스트(Doubly Linked List)

        -정의: 구조는 단일 연결 리스트와 비슷하지만, 포인터 공간이 두 개가 있고 각각의 포인터는 앞의 노드와 뒤의 노드를 가리킨다.

   

(3) 단순 원형 연결리스트(Circular Linked List)

 

단순 원형 연결리스트(Circular LInked List)

        -정의: 일반적인 연결 리스트에 마지막 노드와 처음 노드를 연결시켜 원형으로 만든 구조이다.

 

 

-시간복잡도

 

    (1) 임의의 위치에 원소를 추가: O(1)

 

    (2) 임의 위치의 원소를 제거: O(1)

 

    (3) 임의의 위치의 원소값 확인/변경: O(N)

 

-C의 구조체 + 동적할당을 이용한 구현 (면접 단골문제)

 

-STL List: Doubly Linked List 구조.

 

-문제 백준 1406번 에디터 https://www.acmicpc.net/problem/1406

 

내 코드

 

    - STL list의 erase함수의 return 값: 해당 함수에 의해 지워진 값을 다음 값을 가리키는 iterator

    ( An iterator pointing to the element that followed the last element erased by the function call

 

    - STL list (주의 : end는 마지막 원소가 아닌 끝을 표시하는 것, 마지막 값을 사용하려면 list.end()--를 해줘야 함)

 

        begin(): list의 시작 원소를 가리키는 반복자를 반환한다.

 

        end(): list의 끝 표시 반복자를 반환한다.

 

#include <iostream>
#include <string>
#include <list>

using namespace std;

int main(void) {

	string tmp;
	list<char> arr;

	getline(cin, tmp);
    
    //문자열 list에 저장
	for (int i = 0; i < (int)tmp.size(); i++) arr.push_back(tmp[i]);

	list<char>::iterator now = arr.end();
	int num = 0;
	cin >> num;
    
	for (int i = 0; i < num; i++) {
		char tmp = NULL;
		cin >> tmp;

		if (tmp == 'L') {
			if (now == arr.begin())	continue;
			now--;
		}
		else if (tmp == 'D') {
			if (now == arr.end()) continue;
			now++;
		}
		else if (tmp == 'B') {
			if (now != arr.begin()) {
				now--;
				now = arr.erase(now);
			}
		}
		else if(tmp == 'P') {
			cin >> tmp;
			arr.insert(now, tmp);
		}
	}

	//출력
	list<char>::iterator it = arr.begin();
	for (it = arr.begin(); it != arr.end(); it++) {
		cout << *it;
	}
	
	return 0;
}

 

 

 

 

 

 

 

참고

https://blog.encrypted.gg/725?category=773649

https://ko.wikipedia.org/wiki/%EC%97%B0%EA%B2%B0_%EB%A6%AC%EC%8A%A4%ED%8A%B8