[DS] 6. 리스트

데이터 간 순서가 있고 중간 삽입/삭제가 가능한 자료구조인 리스트의 개념, 사용법, 배열 및 연결 리스트 기반의 구현 방법 등.

Posted Aug 21, 2026

By SDTR

18 min read

[DS] 6. 리스트

리스트(List)?

  
std::list<int> lst;

데이터들 간 순서를 가진 형태의 자료구조. 순서로 인해, 중간에의 삽입/삭제가 가능한 것이 특징.

추상 자료형

데이터 : 임의의 접근 방법이 존재하는, 동일 타입 데이터들 간 순서가 있는 모임.

연산 :

함수	설명
`insert(pos, x)`	`pos` 위치에 데이터 `x`를 삽입한다.
`delete(pos)`	`pos` 위치의 데이터를 삭제한다.
`getEntry(pos)`	`pos` 위치의 데이터를 반환한다.
`isEmpty()`	리스트가 비어있다면 `true`, 아니라면 `false` 반환.
`isFull()`	리스트가 가득 찼으면 `true`, 아니라면 `false` 반환. (배열 리스트용)
`find(x)`	리스트에 `x` 데이터가 있는지 여부를 확인.
`replace(pos, x)`	`pos` 위치의 데이터를 `x`로 교체한다.
`size()`	데이터들의 갯수를 반환한다.
`display()`	모든 데이터들을 출력한다.

사용법 (std::list, std::forward_list)

표준 라이브러리의 List는 이중 연결 리스트 기반이다. 즉, 각 노드가 앞/뒤 노드의 주소 정보를 알고 있다.

단방향 연결 리스트가 필요하다면 Forward List가 있다. 이는 각 노드가 뒤 노드의 주소 정보만을 가진다.

메서드

함수	설명
`front()`	맨 앞의 데이터를 반환한다.
`back()`	맨 뒤의 데이터를 반환한다. (양방향 리스트용)
`push_front(x)`	맨 앞에 데이터 `x`를 삽입한다.
`push_back(x)`	맨 뒤에 데이터 `x`를 삽입한다. (양방향 리스트용)
`pop_front()`	맨 앞의 원소를 삭제한다.
`pop_back()`	멘 뒤의 원소를 삭제한다. (양방향 리스트용)
`empty()`	리스트가 비어 있다면 `true`, 아니라면 `false`.
`clear()`	모든 원소를 삭제한다.
`remove(x)`	값이 `x`인 모든 원소를 삭제한다.
`remove_if(pred)`	조건 `pred`를 만족하는 모든 원소를 삭제한다. 조건의 함수는 `bool` 타입으로의 형변환이 가능해야 한다.
`sort()` / `sort(comp)`	리스트의 원소를 정렬한다. (기본값 오름차순) 조건의 함수는 `bool` 타입으로의 형변환이 가능하고, Strict Weak Ordering을 준수해야 한다.
`reverse()`	원소의 순서를 뒤집는다. 모든 원소를 순회하며 이전/이후 원소의 주소를 `swap`처리한다.
`unique()`	연속해서 중복된 값을 가진 원소를 제거한다.

iterator(반복자) 관련 메서드

함수	설명
`insert(pos, x)`	지정한 `iterator`(`pos`) 위치의 앞에 원소를 삽입한다.
`erase(pos)`	지정한 `iterator`(`pos`) 위치의 원소를 삭제한다.
`insert_after(pos, x)`	지정한 `iterator`(`pos`) 다음 위치에 원소를 삽입한다. (단방향 리스트용)
`erase_after(pos)`	지정한 `iterator`(`pos`) 다음 위치의 원소를 삭제한다. (단방향 리스트용)
`begin()` / `end()`	첫 요소와 마지막 다음 위치를 가리키는 `iterator`(반복자)를 반환한다.
`rbegin()` / `rend()`	역방향 순회를 위한 `reverse_iterator`(역방향 반복자)를 반환한다. (양방향 리스트용)

예제 코드

List

  
#include <iostream>
#include <list>

int main()
{
  std::list<int> numbers = {10, 30};

  numbers.push_front(0);            // 앞에 삽입. 0, 10, 30
  numbers.push_back(40);            // 뒤에 삽입. 0, 10, 30, 40

  auto pos = numbers.begin();
  numbers.insert(++pos, 5);         // index 0++ 자리 삽입.    0, 5, 10, 30, 40
  auto last = numbers.end();
  numbers.erase(--last);            // index size-- 자리 삽입. 0, 5, 10, 30

  std::cout << "[Data] : ";
  for (auto it = numbers.begin(); it != numbers.end(); it++)       // 반복자 기반, 순회
    std::cout << *it << ' ';
  std::cout << std::endl;           // [Data] : 0 5 10 30

  std::cout << "[Data(R)] : ";
  for (auto rit = numbers.rbegin(); rit != numbers.rend(); ++rit)  // 반복자 기반, 역순회
    std::cout << *rit << ' ';
  std::cout << std::endl;           // [Data(R)] : 30 10 5 0
}

[Data] : 0 5 10 30
[Data(R)] : 30 10 5 0

구현

선형 리스트 예제 코드 (배열 기반)

코드를 보면 알겠으나 일단 구현은 했다 정도이지, 배열 기반의 리스트는 실제로 사용하기 어렵다.

인덱스를 통한 임의 접근이 $O(1)$로 매우 빠르긴 하나, 고정 크기인데다, 삽입/삭제 시 원소의 시프트 작업에 큰 오버헤드가 발생하기 때문.

예제 코드

  
#include <iostream>
#define MAX_LIST_SIZE 10

template <typename T>
class ArrayList {
  T  data[MAX_LIST_SIZE];      // 데이터
  int  length;                   // 데이터의 갯수
public:
  ArrayList() { length=0; }      // 생성자

  void insert(int pos, T x)    // 삽입
  { // 자리가 있고, pos가 정상범주 값이라면
    if ((!isFull()) && (pos >= 0) && (pos <= length))
    { // 우선 pos 이후의 값들을 뒤부터 순차적으로 한칸씩 밂.
      for(int i = length; i > pos; i--)
        data[i] = data[i - 1];
      data[pos] = x;             // 만든 자리에 삽입
      length++;                  // 갯수 갱신
    }
    else
      std::cout << "List is full" << std::endl;
  }
    
  void remove( int pos )         // 삭제
  { // 비어있지 않고, pos가 정상범주 값이라면
    if ((!isEmpty()) && (0 <= pos) && (pos < length))
    { // pos 이후의 값들을 앞부터 순차적으로 한칸식 당김.
      for (int i = pos + 1; i < length; i++)
        data[i - 1] = data[i];
      length--;                  // 갯수 갱신
    }
    else
      std::cout << "List is Empty" << std::endl;
  }

  T getEntry(int pos) { return data[pos];} 
  bool isEmpty( ){ return length==0; }
  bool isFull( ) { return length==MAX_LIST_SIZE; }
  void replace( int pos, T x ) { data[pos] = x; }
  int size() { return length; }
  void clear() { length=0; }
  bool find( T item )
  { // 순회 중 타겟이 존재 시 즉시 return true
    for( int i=0 ; i<length ; i++ )
      if( data[i] == item ) return true;
    return false;
  }
  void display( )
  { // 모든 값 출력
    std::cout << "[Data] : ";
    for( int i=0 ; i<size() ; i++ )
      std::cout << data[i] << " ";
    std::cout << std::endl;
  }
};

  
int main()
{
  ArrayList<int> list;

  list.insert(0, 10);   // 10                  (index 0에 삽입)
  list.insert(1, 20);   // 10, 20              (index 1에 삽입)
  list.insert(2, 30);   // 10, 20, 30          (index 2에 삽입)
  list.insert(3, 40);   // 10, 20, 30, 40      (index 3에 삽입)

  list.display();

  list.insert(2, 15);   // 10, 20, 15, 30, 40  (index 2에 삽입)
  list.display();

  list.remove(1);       // 10, 15, 30, 40      (index 1 제거)
  list.display();
}

[Data] : 10 20 30 40
[Data] : 10 20 15 30 40
[Data] : 10 15 30 40

Array List

단순 연결 리스트 예제 코드

이전의 배열 기반 리스트에서 갯수 제한과 데이터 시프트 오버헤드를 없앤 코드이다.

삽입/삭제 시 다음 노드를 가리키는 포인터를 갱신해주면 된다.

여기서 마지막 노드의 link를 첫 번째 노드로 할당해주면 원형 연결 리스트가 된다.

Node 코드

  
#include <iostream>

template <typename T>
class Node {
  Node* link;      // 다음 노드의 주소값
  T data;          // 데이터
public:
  Node(T val = T()) : data(val), link(nullptr) {};   // 생성자
  Node* getLink()           { return link; }
  void setLink(Node* next)  { link = next; }
  void display()            { std::cout << data; } 
  bool hasData(T val)       { return data == val; }

  void insertNext(Node* n)       // 자신의 다음에 새 노드 n 삽입
    if (n) { n->link = link; link = n; }

  Node* removeNext()             // 자신의 다음 노드를 삭제하는 함수
  {
    Node* removed = link;
    if (removed) { link = removed->link; }
    return removed;
  }
};

예제 코드

  
template <typename T>
class LinkedList {
  Node<T> org;                            // 헤드 노드

public:
  LinkedList() : org(T()) {}              // 생성자
  ~LinkedList() { clear(); }              // 소멸자
  void clear() { while(!isEmpty()) delete remove(0); }
  Node<T>* getHead() { return org.getLink(); }
  bool isEmpty() { return getHead()==nullptr; }

  Node<T>* getEntry(int pos)              
  { // pos번째 노드를 반환
    Node<T>* n = &org;
    for(int i=-1 ; i<pos && n ; i++)
      n = n->getLink();
    return n;
  }

  void insert(int pos, Node<T>* n)        
  { // pos 위치에 노드 삽입
    Node<T>* prev = getEntry(pos-1);
    if(prev != nullptr) prev->insertNext(n);
  }

  Node<T>* remove(int pos)                
  { // pos 위치의 노드 삭제
    Node<T>* prev = getEntry(pos-1);
    if(prev != nullptr) return prev->removeNext();
    return nullptr;
  }

  Node<T>* find(T val)                    
  { // 탐색
    for(Node<T>* p=getHead() ; p!=nullptr ; p=p->getLink())
      if(p->hasData(val)) return p;
    return nullptr;
  }

  void replace(int pos, Node<T>* n)       
  { // pos번째 노드를 교체
    Node<T>* prev = getEntry(pos-1);
    if(prev != nullptr) { delete prev->removeNext(); prev->insertNext(n); }
  }

  int size()                              
  { // 리스트의 항목 개수를 반환
    int count = 0;
    for(Node<T>* p=getHead() ; p!=nullptr ; p=p->getLink())
      count++;
    return count;
  }

  void display()                          // 모든 값 출력
  {
    std::cout << "[Data] : ";
    for(Node<T>* p=getHead() ; p!=nullptr ; p=p->getLink())
    {
      p->display();
      std::cout << " ";
    }
    std::cout << std::endl;
  }
};

  
int main()
{
  LinkedList<int> list;

  list.insert(0, new Node<int>(10));   // 10
  list.insert(1, new Node<int>(20));   // 10, 20
  list.insert(2, new Node<int>(30));   // 10, 20, 30
  list.insert(3, new Node<int>(40));   // 10, 20, 30, 40
  list.display();

  list.insert(2, new Node<int>(15));   // 10, 20, 15, 30, 40
  list.display();

  delete list.remove(1);               // 10, 15, 30, 40
  list.display();

  list.replace(2, new Node<int>(35));  // 10, 15, 35, 40
  list.display();
}

[Data] : 10 20 30 40
[Data] : 10 20 15 30 40
[Data] : 10 15 30 40
[Data] : 10 15 35 40

Single-Ended Linked List

이중(양방향) 연결 리스트 예제 코드

노드가 다음 노드의 주소값뿐만 아니라 이전 노드의 주소값도 가지는 형태이다.

이로 인해 메모리를 조금 더 사용하긴 하나, 역방향 탐색도 가능해진다.

Node 코드

  
template <typename T>
struct Node
{
  Node* prev;    // 이전 노드의 주소값
  Node* next;    // 다음 노드의 주소값
  T data;        // 데이터

public:
  Node(T val = T(), Node<T>* p = nullptr, Node<T>* n = nullptr) 
    : data(val), prev(p), next(n) {}
  Node* getPrev()        { return prev; }
  Node* getNext()        { return next; }
  void setPrev(Node* p)  { prev = p; }
  void setNext(Node* n)  { next = n; }
  void display()         { std::cout << " <" << data << ">"; }
  bool hasData(T val)    { return data == val; } 
    
  void insertNext(Node* newNode)
  { // 자신의 다음에 새로운 노드 추가.
    if (newNode != nullptr) {
      newNode->prev = this;
      newNode->next = this->next;
      if (this->next != nullptr) this->next->prev = newNode;
      this->next = newNode;
    }
  }

  Node* remove()
  { // 현재 노드를 연결 리스트에서 제거+반환.
    if (this->prev != nullptr) this->prev->next = this->next;
    if (this->next != nullptr) this->next->prev = this->prev;
    return this;
  }
};

예제 코드

  
template <typename T>
class DblLinkedList {
  Node<T> org;                            // 헤드 노드
public:
  DblLinkedList() : org(T()) {}           // 생성자
  ~DblLinkedList() { clear(); }           // 소멸자
  void clear() { while(!isEmpty()) delete remove(0); }
  Node<T>* getHead() { return org.getNext(); }
  bool isEmpty() { return getHead()==nullptr; }

  Node<T>* getEntry(int pos)             
  { // pos번째 노드 반환
    Node<T>* n = &org;
    for(int i=-1 ; i<pos && n ; i++)
      n = n->getNext();
    return n;
  }

  void insert(int pos, Node<T>* n)       
  { // pos 위치에 노드 삽입
    Node<T>* prev = getEntry(pos-1);
    if(prev != nullptr) prev->insertNext(n);
  }

  Node<T>* remove(int pos)               
  { // pos 위치의 노드 삭제
    Node<T>* n = getEntry(pos);
    if(n != nullptr) return n->remove();
    return nullptr;
  }

  Node<T>* find(T val)                   
  { // 값이 val인 노드 탐색
    for(Node<T>* p=getHead() ; p!=nullptr ; p=p->getNext())
      if(p->hasData(val)) return p;
    return nullptr;
  }

  void replace(int pos, Node<T>* n)      
  { // pos 위치의 노드 교체
    Node<T>* prev = getEntry(pos-1);
    if(prev != nullptr && prev->getNext() != nullptr) {
      delete prev->getNext()->remove();
      prev->insertNext(n);
    }
  }

  int size()                              
  { // 리스트의 전체 노드 수 반환
    int count = 0;
    for(Node<T>* p=getHead() ; p!=nullptr ; p=p->getNext())
      count++;
    return count;
  }

  void display()                          
  { // 모든 값 출력
    std::cout << "[Data] : ";
    for(Node<T>* p=getHead() ; p!=nullptr ; p=p->getNext()) {
      p->display();
      std::cout << " ";
    }
    std::cout << std::endl;
  }
};

  
int main()
{
  DblLinkedList<int> list;

  list.insert(0, new Node<int>(10));   // 10
  list.insert(1, new Node<int>(20));   // 10, 20
  list.insert(2, new Node<int>(30));   // 10, 20, 30
  list.insert(3, new Node<int>(40));   // 10, 20, 30, 40
  list.display();

  list.insert(2, new Node<int>(15));   // 10, 20, 15, 30, 40
  list.display();

  delete list.remove(1);               // 10, 15, 30, 40
  list.display();

  list.replace(2, new Node<int>(35));  // 10, 15, 35, 40
  list.display();
}

[Data] : 10 20 30 40
[Data] : 10 20 15 30 40
[Data] : 10 15 30 40
[Data] : 10 15 35 40

Double-Ended Linked List

특징

단순 연결 리스트는 대신 맨 처음 노드부터 순방향으로만 탐색이 가능하기에, 임의 접근 속도가 $O(n)$으로 느리다는 단점이 있다. 대신 데이터의 삽입/삭제는 대상 노드의 위치를 알고 있다면, $O(1)$로 상당히 빠르다. 다만 대상 노드의 위치를 찾기 위해서는 탐색이 선행되어야 한다.

양방향 연결 리스트는 역방향 탐색도 가능하다. 이전 노드 정보도 가지고 있기에. 대신 (이전 노드 정보를 담을 메모리가 필요하기에) 그만큼의 메모리를 더 차지하게 된다.

또한 메모리의 연속성을 가지지 않으므로, 캐시 효율성이 떨어진다는 단점도 존재한다.

사용례

음악 플레이어의 재생목록
해시 테이블에서의 충돌 해결 방법중 하나 (해시 충돌 시 같은 해시값의 데이터들끼리 연결 리스트화)
이외 데이터의 삽입/삭제가 빈번한 모든 경우.

Computer Science, Data Structure

This post is licensed under CC BY 4.0 by the author.

[DS] 6. 리스트

리스트(List)?

추상 자료형

사용법 (std::list, std::forward_list)

메서드

iterator(반복자) 관련 메서드

예제 코드

구현

선형 리스트 예제 코드 (배열 기반)

단순 연결 리스트 예제 코드

이중(양방향) 연결 리스트 예제 코드

특징

사용례

댓글

Trending Tags