[자료구조 공부] 자바스크립트 연결 리스트(Linked List) #4

☘️ 연결 리스트 사용하는 이유

그 전 글에서 배열을 알아보았는데, 배열 같은 경우 원하는 위치에 데이터를 추가하고 삽입하는 경우에 시간 복잡도가 O(n) 으로 크다.

 

그래서 요소 추가와 삭제가 반복되는 로직 같은 경우는 배열을 사용하지 않고 연결 리스트를 사용하고,

배열은 탐색이 많은 로직에서 사용하면 좋다.

 

배열 - 탐색 유리
연결 리스트 - 요소 추가, 삭제 유리

 

☘️ 연결 리스트란?

연결 리스트 정의

 

연결 리스트는 각 요소를 포인터로 연결하여 관리하는 선형 자료구조로

각 요소는 노드라고 부르고, 각 노드에는 해당 노드의 값이 있는 데이터 영역과 다음 노드를 가리키는 포인터 영역으로 구성된다.

그리고 첫번째 노드를 헤드(Head)라고 부른다.

 

연결리스트의 핵심 로직은

• 요소 찾기
• 요소 추가
• 요소 삭제

로 이루어져 있다.

 

연결 리스트 특징

연결 리스트는 배열과 다르게 요소를 제한없이 추가할 수 있으며,

배열은 메모리에서 연속적으로 배치되어 있으나 연결 리스트는 순차적이지 않고 데이터가 퍼져있다.

바로 이렇게 퍼져 있는 데이터를 포인터를 사용해서 다음 노드를 알 수 있다.

 

이러한 차이로

배열
탐색 O(1), 추가 및 제거 O(n)
연결 리스트
탐색 O(n), 추가 및 제거 O(1)

 

시간 복잡도가 서로 다른 것을 확인할 수 있다.

 

연결 리스트 종류

연결 리스트에는 3가지가 있다.

• Singly Linked List (단일 연결 리스트)
• Doubly Linked List (이중 연결 리스트)
• Circular Linked List (환형 연결 리스트)

 

☘️ Singly Linked List (단일 연결 리스트)

단일 연결 리스트는 연결 리스트의 기본형이며 첫 번재 노드인 헤드(Head)부터 마지막 노드인 테일(Tail)까지 단방향으로 이어진다.

여기서 테일(Tail)은 포인터 영역이 NULL 로 더 이상 가리키는 곳 or 갈 곳이 없는 마지막이라는 의미이다.

 

요소 찾기

요소를 찾는 방법은

헤드 포인터부터 시작하여 다음 영역의 데이터가 만약 내가 찾던 요소가 아니라면 해당 요소의 포인터 영역을 통해 다음 요소로 넘어간다.

이러한 로직을 반복하여 원하는 요소를 찾는다.

1. 헤드 포인터부터 시작한다.
2. 해당 요소의 데이터가 내가 찾는 데이터가 아니라면
3. 포인터 영역을 통해 다음 요소로 넘어간다.
4. 2, 3번을 반복한다.
5. 만약 해당 요소의 데이터가 내가 찾는 데이터라면 요소 찾기 완료
6. 테일(Tail) 영역 까지 왔는데 내가 찾는 데이터가 없으면 찾는 요소 없음

 

요소 추가

요소를 추가하는 방법은

먼저 (가)요소와 (다)요소가 있을 때, 이 둘 사이에 (나)요소를 추가하기 위해서

1. (나)요소의 포인터 영역이 (다)요소를 가리킨다.
2. (다)요소를 가리키던 (가)요소의 포인터를 (나)요소로 가리킨다.

 

요소 삭제

요소를 삭제하는 방법은

차례대로 (가)요소, (나)요소, (다)요소가 있을 때, (나)요소를 삭제하기 위해서

1. (나)요소를 가리키던 (가)요소의 포인터를 (다)요소를 가리킨다.
2. 삭제할 요소인 (나)요소를 메모리상에 지워버린다.

 

☘️ Doubly Linked List (이중 연결 리스트)

이중 연결 리스트는 양방향으로 이어지는 연결 리스트로

기존 Singly Linked List에서 이전 노드를 가리키는 포인터가 추가된 것이 Doubly Linked List 이다.

 

그러나 단일 연결 리스트에서 포인터가 추가 되어 크기가 조금 커졌다는 단점이 있다.

 

요소 추가

요소를 추가하는 방법은

먼저 (가)요소와 (다)요소가 있을 때, 이 둘 사이에 (나)요소를 추가하기 위해서

1. (나)요소가 다음 노드로 (다)요소를 가리킨다.
2. (다)요소를 다음 노드로 가리키던 (가)요소의 다음 노드를 (나)요소를 가리킨다.
3. 이전 요소로 (가)요소를 가리키던 (다)요소의 이전 노드를 (나)요소를 가리킨다.
4. (나)요소가 이전 노드로 (가)요소를 가리킨다.

 

요소 삭제

요소를 삭제하는 방법은

차례대로 (가)요소, (나)요소, (다)요소가 있을 때, (나)요소를 삭제하기 위해서

1. (나)요소를 다음 노드로 가리키던 (가)요소의 다음 노드를 (다)요소로 가리킨다.
2. (나)요소를 이전 노드로 가리키던 (다)요소의 이전 노드를 (가)요소로 가리킨다.
3. (나)요소를 메모리 상에서 삭제한다.

 

☘️ Circular Linked List (환형 연결 리스트)

Circular Linked List(환형 연결 리스트)는 단일 or 이중 연결 리스트에서 Tail 이 Head 로 연결되는 리스트이다.

 

요소를 탐색, 추가, 삭제하는 방법은 위에 작성한 글과 같다.

 

☘️ 연결 리스트 코드로 표현하기

연결 리스트를 자바스크립트 코드로 다음과 같이 구현할 수 있다.

(예외 처리까지 완벽하게 구현X)

코드 실행 결과

그러나 실제 코딩테스트에서는 직접 연결 리스트를 구현해서 사용하는 경우는 별로 없다고 한다.

 

---

 

해당 게시물은 프로그래머스 - 코딩테스트 광탈 방지 A to Z : JavaScript 강의를 참고하여 작성한 글입니다. (유료강의)

코딩테스트 광탈 방지 A to Z : JavaScript