[알고리즘 스터디 with 케이시] 선형 리스트 - 연결 리스트

• 추가와 삭제가 빈번한 자료구조는 연결리스트를 추천한다.
• 배열은 탐색이 빈번한 경우

 정의 - 연결 리스트

• 연결 리스트는 각 요소를 포인터로 연결하여 관리하는 선형 자료구조다.
• 각 요소는 노드라고 부르며 데이터 영역과 포인터 영역으로 구성된다.
• 첫번째 노드는 HEAD라고 부른다.

특징

• 메모리가 허용하는 한 요소를 제한없이 추가할 수 있다.
• 탐색은 O(n)이 소요된다.
• 요소를 추가하거나 제거할 때는 O(1)이 소요된다.
• 종류
  • Singly Linked List
  • Doubly Linked List
  • Circular Linked List

배열과 차이점

메모리 차이

• 배열 - 연속적인 메모리 영역 사용
• 연결 리스트 - 각 영역이 떨어져 있고 이를 참조하기 위해 포인터 사용

요소 추가 & 삭제

• 배열 - 선형 시간 O(N)
• 연결 리스트 - O(1)

 연결리스트 요소 삭제

https://user-images.githubusercontent.com/50472122/180375625-db1f0600-368d-4b5a-9b00-4bb2f3dc5787.mov

순서

1. 지우고자 하는 노드를 선택 (A)
2. A 이전 노드의 다음 노드를 A.next로 선택
3. A = nil

연결 리스트 요소 추가 

https://user-images.githubusercontent.com/50472122/180376797-e7e78840-0faa-49da-8875-b7700e5195d5.mov

순서

1. 삽입하고자 하는 인덱스 의 노드 지정 A
2. 새로운 노드 생성 N
3. 새로운 노드 N의 다음 노드를 A로 지정
4. Index - 1 의 노드 P의 다음 노드를 N으로 지정

 

단일 연결 리스트

• 헤드에서 테일까지 단방향
• 가장 단순한 형태의 연결 리스트

 

요소 찾기 

O(N)이 걸린다.
아래는 JS 코드긴 한데, 이해가 어렵지는 않은 코드여서 공유합니다. 

이중 연결 리스트

• 양방향으로 이어지는 연결 리스트
• 단일 연결 리스트보다 조금 더 구조가 크다.
• 다음 포인터가 있는것과 비슷하게 이전 노드 포인터가 있다. 

좀 잔인한 사진..

환형 링크드 리스트

테일의 포인터가 헤드를 가리키고 있다는 점만 뺴고 싱글과 더블 링크드 리스트와 비슷함.

스위프트로 구현한 링크드 리스트와 그 기능들