c++ 기초 - 리스트 (list)

리스트 (list)

STL의 리스트는 시퀀스 컨테이너로 vector와 동일하게 순서를 유지하며 데이터를 선형적으로 관리한다.
노드 기반의 컨테이너이며 이중 연결 리스트로 구현되어 있다.

선언

list<자료형> 리스트이름;

 

동작 원리

노드 기반의 컨테이너로 메모리상 연속적으로 위치하지 않으며 각 요소(노드)들은 데이터와 이전, 다음 노드의 주소를 가지고 있다.

 

노드 구조

노드는 데이터와 연결 정보(포인터)로 구성된다. 

class Node
{
public:
    Node* _next; // 다음 노드 가리키는 주소
    Node* _prev; // 이전 노드 가리키는 주소
    int _data;
}

 

좀 더 이해하기 쉽게 도식화 한 그림이다. 각 노드들은 메모리 상 떨어져서 위치하며 next와 prev 포인터로 노드들이 연결되어 있는 방식이다.

Dummy Node

처음 요소의 prev는 어떻게 되어 있을까? 기본적으로 시작의 prev와 끝의 next에는 dummy 노드가 들어있다. dummy 노드는 유효 범위, 즉 시작과 끝을 표현하고자 사용하게 된다. 

 

실제로 맨 처음 값 기준으로 앞으로 가는 것을 시도하거나 맨 마지막 값(iterator end)을 기준으로 다음 값으로 가는 것을 시도하면 error가 난다.  그래서 dummy는 end 표현을 하면서 잘못된 접근을 막기 위해 있다고 볼 수 있다. (dummy로 연결되어 있다고 원형 리스트처럼 접근할 수 있다는 개념은 아니다.)

 

dummy 노드는 연산들을 더 단순히 구현할 수 있다는 장점을 가져온다.

 

dummy 노드가 존재하지 않는다면 데이터를 조회하거나 추가할 때 리스트가 비어 있는 경우와 그렇지 않은 경우를 나누어 처리해야한다. 리스트가 비어 있는 경우 head가 NULL값을 가지므로, head->next와 같은 참조가 불가능했기 때문이다. 더미 노드를 추가함으로써 head->next가 NULL을 가져도 참조가 가능해져서 조건을 나누지 않고 연산을 구현할 수 있다.

 

임의 접근 👎

vector는 연속된 공간에 있어서 주소를 계산해 쉽게 임의 접근이 가능했다.

 

list는 데이터가 메모리에 분리되어 저장되어 있기 때문에 특정 위치의 요소를 찾을려면 처음 노드에서 포인터로 노드를 하나씩 타고 가면서 찾을 수 밖에 없기 때문에 비효율적이다. (따라서 임의 접근을 허용하지 않는다.)

list<int> li;

// li[100]; // 임의 접근 x!

 

벡터처럼 산술적으로 주소를 바로 계산해서 다른 요소에 접근하는 것이 안되기 때문에 산술 연산을 지원하지 않는다. (단, 1칸만 이동하는 연산은 제공한다. (ex. ++))

list<int>::iterator it = li.begin() + 10; // 에러!
list<int>::iterator it = li.begin()++; // 이건 가능!

 

삽입/삭제 👍

vector의 경우 연속된 공간에 있어야 해서 중간에 삽입이나 삭제가 일어나면 다른 요소들도 모두 옮겨줘야해 비효율적이었다.

 

리스트의 경우 연속된 공간에 있을 필요가 없으므로 효율적인 삽입 삭제가 가능하다. (처음, 중간, 끝 상관 없이!) 노드의 이전 포인터와 이후 포인터만 잘 처리해주면 된다.

 

❓ 그럼 중간에 요소를 삽입하고 삭제하는 것이 굉장히 효율적이라는 것인가?

삽입과 삭제 자체가 효율적이라는 의미지 임의 접근과 엮여있는 경우 효율적이라고 하기 어렵다. 중간 삽입과 삭제를 위해서는 해당 요소를 찾아가는 과정(임의 접근)을 거친다. 따라서 전체적으로 이야기하자면 효율적이라 이야기하기 어렵다. 대신 삭제할 대상을 iterator로 들고 있거나 저장해두었다가 지우는 경우 임의 접근 과정이 필요 없기 떄문에 빠르게 데이터 삭제가 가능하다. 

자주 사용하는 멤버함수

다른 함수의 경우 다음 사이트에서 필요할 때 찾아보면 된다.

list 클래스 | Microsoft Learn

 

요소 접근

• front(): 맨 앞 요소 반환
• back(): 맨 뒤 요소 반환
• begin(): 맨 앞 요소 가리키는 iterator 반환
• end(): 맨 마지막 다음 요소 가리키는 iterator 반환

요소 삽입 삭제

• push_back(): 맨 뒤 요소 삽입
• push_front(): 맨 앞 요소 삽입
• pop_front(): 맨 앞 요소 제거
• pop_back(): 맨 마지막 요소 제거
• insert(iterator, 값): iterator가 가리키는 위치에 요소 삽입 (이외에도 다양한 매개변수를 지원하기 때문에 필요에 따라 찾아서 사용하면 될듯하다.)

using namespace std;
#include <list>

int main()
{
    list li;

    li.insert(li.begin(), 100); // 시작 위치에 100 삽입
}

• erase(iterator): iterator가 가리키는 요소 삭제 (삭제한 원소의 다음 요소 가리키는 iterator 반환)

li.erase(li.begin());

• clear(): list 모든 요소 제거
• remove(값): 값과 같은 요소 모두 제거

li.remove(10); // value와 일치하는 모든 요소들 삭제