Algorithm (연결 리스트)

(본 글은 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 를 참조)