[C++] 리스트(List)
👻 리스트
리스트(List)는 STL 컨테이너 중 하나이며 연결 리스트(Linked List)라고도 불리며 단일 연결 리스트, 이중 연결 리스트, 원형 연결 리스트가 있다. 벡터와 비슷하지만 사용 빈도는 벡터보다 낮다.
#include <list>
list<int> li;
벡터처럼 리스트 라이브러리를 추가해줘야 사용이 가능하고 사용 방법은 벡터와 똑같다.
- push_back : 가장 뒤에 요소를 추가한다.
- push_front : 가장 앞에 요소를 추가한다.
- size : 리스트의 크기를 반환한다.
- front : 가장 첫 번째 요소를 반환한다.
- back : 가장 마지막 요소를 반환한다.
- begin : 가장 첫 번째 요소를 가리킨다.
- end : 가장 마지막 요소의 다음 주소를 가리킨다.
- insert : 특정 위치에 요소를 추가한다.
- erase : 특정 위치에 있는 요소를 삭제한다.
- pop_back : 가장 마지막 요소를 삭제한다.
- pop_front : 첫 번째 요소를 삭제한다.
- remove : 특정 값과 일치하는 모든 요소를 일괄 삭제한다.
대부분 자주 사용하는 함수들이며 벡터와 다르게 capacity 함수는 존재하지 않는다. 동적 배열이 아니기 때문이다.
🌱 list의 동작 원리
리스트는 동적 배열이 아닌 일종의 노드들로 이루어진 형식이다. 배열처럼 메모리에 데이터가 연속적으로 존재하지 않고 위치는 각자 달라도 각 노드가 다음 주소의 정보를 가지고 있어 서로 연결되어있는 식이다. 단일 연결 리스트는 단방향으로만, 이중 연결 리스트는 양방향으로, 원형 연결 리스트는 이중 연결 리스트에 추가적으로 마지막 요소가 첫 번째 요소를 가리키는 순환식으로 설계되어있다.
리스트를 이루는 노드의 대략적인 구성은 다음과 같다.
class Node {
public:
Node* _next;
int _data;
}
_data에는 해당 노드의 정보가 담겨있고 _next에는 다음 노드의 주소값이 들어있다. 위의 설계도는 단일 연결 리스트일 때를 의미하고 이중 연결 리스트나 원형 연결 리스트라면 이전 노드의 주소값이 추가로 들어있다고 볼 수 있다.
class Node {
public:
Node* _next;
Node* _prev;
int _data;
}
하지만 리스트의 구조가 자유로운 대신 데이터가 정리되어있지 않고 임의 접근(Random Access)이 불가해 동적 배열보다는 탐색하기 어렵다.
🌱 삽입과 삭제
이러한 리스트의 구조는 벡터와 다르게 중간 삽입, 삭제 그리고 처음의 삽입, 삭제가 아주 간편하고 빠르다. 리스트의 삽입과 삭제는 노드가 저장하고 있는 포인터의 값만 변경해주면 쉽게 할 수 있다.
단, 중간 삽입, 삭제가 빠르다는 것은 해당 위치를 알고있다는 전제하에 성립되는 설명이다. 지점을 확실하게 알지 못하면 반복문을 통해 탐색을 하는 과정이 필요하게되고 그로 인해 탐색이 느리다는 설명이 성립된다. 탐색 부분과 삽입, 삭제 부분을 나눠서 이해해야 할 필요가 있다.
🌱 반복자
리스트에서 이터레이터는 벡터와 다르게 제한되는 기능이 많다. 연속되어 저장된 게 아니기 때문에 임의의 수를 직접 더하는 연산은 불가능하다.
list<int>::iterator it = li.begin() + 10; // 불가능
그러나 이전 노드의 주소와 다음 노드의 주소는 알고 있기 때문에 1씩 더하거나 빼는 것은 증감 연산자를 이용한다면 가능하다.
list<int>::iterator itTest1 = --itBegin; // X
list<int>::iterator itTest2 = --itEnd; // O
list<int>::iterator itTest3 = ++itEnd; // X
단, 첫 노드의 이전 주소로 이동한다거나 마지막 노드의 다음 주소로 이동하는 것은 불가능하다. 이중 연결 리스트의 경우 마지막 노드의 다음 주소엔 더미 노드(헤더 노드)가 연결되어 있다. 리스트의 마지막 노드의 다음 주소인 end() 값이 들어있는 노드이다. 그래서 원형이 아닌 이상 첫 노드와 마지막 노드 간의 이동은 불가능하다.
// 이중 : [1] <-> [2] <-> [3] <-> [4] <-> [5] <-> [6] <-> [ _Myhead : end() ](더미 노드) <->
👻 글을 마치며
이번 시간에는 리스트에 대해 알아보았다. 대략적인 자료구조 자체의 이론은 알고 있었지만 항상 코드로 연결시키기 어려웠는데 개념의 개념부터 알고나니 코드를 작성할 때에도 자료구조가 한 눈에 보이는 느낌을 받았다. 리스트가 어디에 쓰일지도 생각을 한 번 해봐야 할 것 같다. 그리고 직접 구현하는 거 너무 어려움 ㅠㅠ
Leave a comment