Algorithm (연결 리스트)

김정욱·2020년 10월 9일

Algorithm - 문제

목록 보기

9/249

(본 글은 https://www.youtube.com/watch?v=C6MX5u7r72E&list=PLtqbFd2VIQv4O6D6l9HcD732hdrnYb6CY&index=5 를 참조)

[ 개념 ]

: 값과 포인터를 가지고 노드간 서로 연결된 선형 자료구조

[ 특징 ]

N 번째 원소를 확인 / 변경 => O(N)

임의의 위치에 원소를 추가 / 제거 => O(1)

배열과 같은 '선형 자료구조' (배열과 자주 비교된다)

C++ STL에서 list를 사용

STL 사용 못하는 코테에서는 구현해서 사용해야함
1) 정석 연결 리스트
2) 야매 연결 리스트(추천)

[ 종류 ]

1) 단일 연결 리스트
: 각 노드가 자신의 다음 노드의 주소 보유
2) 이중 연결 리스트
: 각 노드가 자신의 이전 / 다음 노드의 주소 보유
3) 원형 연결 리스트
: 처음과 끝이 연결된 리스트 / 단일, 이중 모두 가능

[ 배열과 차이 ]

다음 혹은 이전 주소를 저장해야 하기 때문에 N에 비례한 크기 필요!

배열은 접근이 효율적 / 연결 리스트는 추가,삭제가 효율적

연결 리스트는 추가/제거가 많이 일어날때 많이 사용

[ 구현- 야매 연결 리스트 ]

[ 구조 ]
- dat[] : 데이터 저장
- pre[] : 이전 노드 주소(여기서는 배열 인덱스) / default = -1
- nxt[] : 다음 노드 주소(여기서는 배열 인덱스) / default = -1
- unused : 연결 리스트 마지막 요소 다음 위치를 가리키는 값
(추가하면 증가 필요 / default = 1)

0번째 인덱스는 더미노드를 둔다
(최초 삽입 / 삭제시 예외처리보다 이게 편하기 때문)
: 더미노드의 nxt로 첫 번째 노드를 가리키게 한다

[ 함수 ]

순회 함수(traverse)

insert 함수
const int MX = 1000005;
int dat[MX], pre[MX], nxt[MX];
int unused = 1;

...

void insert(int addr, int num){
    dat[unused] = num;
    pre[unused] = addr;
    nxt[unused] = nxt[addr];
    // 마지막 노드는 nxt[addr]이 없기에 예외처리 필요
    if(unused != -1) pre[nxt[addr]] = unused;
    nxt[addr] = unused;
    unused++;
}
erase 함수
const int MX = 1000005;
int dat[MX], pre[MX], nxt[MX];
int unused = 1;

...

void erase(int addr){
    nxt[pre[addr]] = nxt[addr];
    // 마지막 노드는 nxt[addr]이 없기에 예외처리 필요
    if(nxt[addr] != -1) pre[nxt[addr]] = pre[addr]; 
    // 제거 후 메모리 낭비가 되므로 야매 리스트라고 부르는 것임
    // 현업에서 사용은 X / 코테에서 사용 O
}
[ STL List 사용하기 ]

: STL List는 이중 연결 리스트로 구현되어 있다
[ 생성 ]
  list<int> L;
iterator

L.begin() / L.end()
  list<int>::iterator t = L.begin();

  /* C++11 이상부터 가능 */
  auto t = L.begin();
[ 내장 함수 ]

push_front / push_back

O(1)
  L.push_front(10); // 맨 앞에 10 삽입
  L.push_back(12); // 맨 뒤에 12 삽입

  /* iterator로 값 확인 */
  cout << *t << '\n' // 10
pop_front / pop_back

O(1)
  L.pop_front(); // 맨 앞 요소 삭제
  L.pop_back(); // 맨 뒤 요소 삭제
insert()
  // 1 3 4 상태에서 it는 3을 가리키고 있음
  L.insert(it,2); // it가 가리키는 곳에 2 삽입
  // 1 2 3 4 가 되고 it는 여전히 3을 가리킨다
erase()
: 제거한 다음 원소의 위치를 반환
  // 1 2 3 4 상태에서 it는 3을 가리킨다
  it = L.erase(it);
  // 1 2 4 가 되고 it 는 4를 가리킨다.

  // 1 2 3 4 상태에서 it는 3을 가리킨다
  L.erase(it);
  // 1 2 4 가 되고, it는 여전히 3을 가리킨다
[ List 순회 ]
 for(list<int>::iterator it = L.begin() ; it != L.end() ; it++)
   cout << *it << ' ';

       /* C++11 부터 */
 for(auto i : L) cout << i << ' ';
``(본 글은 https://www.youtube.com/watch?v=C6MX5u7r72E&list=PLtqbFd2VIQv4O6D6l9HcD732hdrnYb6CY&index=5 를 참조)