링크드 리스트

데이터를 집어넣는 방법

• 메모리 확보 후 연속된 공간에 채워넣기 vs 필요할 때마다 메모리를 할당받아 데이터를 저장

  • 전자는 배열이고 후자는 연결리스트 즉, Linked List 라고 함

노드 정의

struct node{
  int value;
  struct node* next;
}

garbage collector

• 더 이상 참조되지 않는 메모리를 garbage라고 하고, 이러한 garbage를 수거하는 작업은 garbage collector가 진행한다.

• 자바,파이썬은 쓰레기 수집(garbage collection)이 자동으로 이루어지지만,
  c++ 은 프로그래머가 직접 free, delete 키워드로 삭제해야 한다.

링크드 리스트의 삭제

1) 헤드를 삭제

기존 헤드를 담을 변수 생성 → 변수 이용해서 헤드의 next를 헤드로 지정
→ free나 delete 키워드로 기존 헤드 삭제

cf. 기존 헤드를 삭제하지 않으면 데이터 누수가 발생함

2) 테일을 삭제

기존 테일의 이전 노드가 null을 가리키도록 수정 → 이전노드를 새로운 테일로 지정
→ 기존 테일 값 삭제

cf. 테일을 삭제하려면 테일 이전 노드의 주소를 알기 위해 헤더에서부터 next를 반복해야 한다.

이처럼 싱글리 링크드 리스트에서 테일을 삭제하는건 비효율적이다.

but, 더블리 링크드 리스트는 이전 노드의 주소로 접근하면 되므로 바로 할 수 있다!

head 노드 삭제

• garbage collector : 기존에 할당 받았던 메모리 공간을 시스템에 돌려줌(삭제함)
  • 완전히 시스템에서 삭제하기 위해 가비지 콜랙터로 free 또는 delete 를 한다.
  • 나중에 필요할 때 삭제된 데이터는 다시 호출 가능하다.

tail 노드의 노드 삭제

요약 : tail 노드의 노드를 삭제하려는 경우
싱글리리스트:O(n) => 비효율적. 맨앞에서 부터 일일이 찾아갸아함.
더블리링크드리스트:O(1) => prev 노드를 알고 있기 때문

• 싱글리 리스트의 경우, tail 바로 노드는 가급적 삭제하지 말것.

  • 어떤 노드를 삭제하기 위해선, 그 앞과 뒤의 위치 정보를 알아야 하는데 따로 위치를 저장해놓지 않는 이상은 그 위치를 바로 알아낼 수 있는 방법이 없다.

  • 따라서 tail 이전 노드의 정보를 알수 없기 때문에, 앞 뒤의 연계를 해주는 과정이 비효율적이다.

    => 정리하자면, 링크드 리스트 특성상 맨앞 노드부터 시작해서 맨 끝노드인 tail 이전 노드에 접근해야 하기 때문에 최악의 경우로 O(n) 이 걸려서 비효율적이다.

• 싱글리 리스트에서는 임의의 위치의 노드를 삭제하는 것도 비효율적이다.

• But, 임의의 위치의 노드 정보(인덱스 값) 를 주고, 그 다음 노드를 삭제하는 연산은 금방할 수 있다.

  • 삭제할 노드의 앞 뒤 정보를 알고있기 때문에 바로 삭제 가능함