누구나 자료구조와 알고리즘 - (11) 노드 기반 자료구조: 연결 리스트

 

 

 

 

 

연결 리스트(linked list)

 

1.1. 연결 리스트가 유용한 순간

연결 리스트는 배열과 상당히 유사하지만 자료 구조의 성능에 큰 차이가 있다. 가령 세 번째 node에 있는 값을 읽거나 검색하기 위해서는 첫 번째부터 접근하여 순차적으로 진행해야 하므로 O(N)이다. 따라서 읽기와 검색에서는 유의미한 차이가 없지만 연결 리스트는 삽입에서 빛을 발휘한다.

 

배열에서 최악의 시나리오는 인덱스 0에 데이터를 삽입하거나 삭제할 때이다. 나머지 데이터를 한 셀씩 오른쪽으로 옮겨야 하기 때문에 효율성은 O(N)이 된다. 반면 연결 리스트는 딱 한 단계인 O(1)만 걸린다. 삽입하는 경우 배열처럼 한 셀씩 옮기는 것이 아니라 기존 리스트 앞에 새 노드를 생성하고 노드가 이전의 첫 번째 노드를 가리키도록 만들면 된다. 삭제하는 경우에 삭제하는 셀 그 다음부터 시작하도록 연결 리스트를 바꾸면 된다.

 

배열과 연결 리스트의 삽입, 삭제를 비교하면 다음 표와 같다.

시나리오	배열	연결 리스트
앞에 삽입/삭제	최악의 경우	최선의 경우
중간에 삽입/삭제	평균적인 경우	평균적인 경우
끝에 삽입/삭제	최선의 경우	최악의 경우

 

💡 삭제된 노드를 처리하는 방식

삭제된 노드를 처리하는 방식은 프로그래밍 언어마다 다르나 어떤 언어에서는 쓰이지 않는 노드를 자동으로 감지해 "가비지 컬렉트"하고 메모리를 해제한다.

 

 

 

1.2. 효율적으로 연결 리스트 사용하기

시나리오	배열	연결 리스트
읽기	O(1)	O(N)
검색	O(N)	O(N)
삽입	O(N) (끝에서 하면 O(1))	O(N) (앞에서 하면 O(1))
삭제	O(N) (끝에서 하면 O(1))	O(N) (앞에서 하면 O(1))

 

이 표만 보면 배열과 효율성에 별 차이가 없다. 연결 리스트가 효과적으로 쓰이려면 실제 삽입과 삭제 단계가 O(1)라는 점을 활용해야 한다. 전형적인 연결 리스트에서 일부를 조금 수정해 연결 리스트를 향상시킬 수 있다.

 

이중 연결 리스트는 각 노드에 2개의 링크가 있다는 점만 제외하면 연결 리스트와 비슷하다. 각각의 링크는 다음 노드와 앞 노드를 가리킨다. 그래서 전형적인 연결 리스트는 앞으로만 이동할 수 있지만 이중 연결 리스트는 앞과 뒤 모두 이동할 수 있다. 이중 연결 리스트로 큐를 구현함으로써 삽입과 삭제에 O(1)만 걸린다.

 

 

 

---

출처

제이 웹그로우, 누구나 자료구조와 알고리즘 (길벗, 2021)

 

 

 

 

---

개인적으로 공부한 내용을 정리하는 블로그로
잘못된 개념을 게시하지않도록 주의하고 있으나 오류가 있을 수 있습니다.