[자구] 배열과 연결 리스트

배열

배열이란 일정한 메모리 공간을 차지하는 여러 요소들이 순차적으로 나열된 자료구조를 말한다.

각 요소에는 0부터 시작하는 고유한 순서 번호인 인덱스가 매겨지며, 배열의 요소를 식별할 수 있다.

• 조회: 인덱스로 특정 요소 접근 → O(1)
• 삭제, 수정: 순차적 검색 → O(n)

 

---

연결 리스트

연결리스트는 노드의 모음으로 구성된 자료구조이다.

• 연결리스트의 노드란, 저장하고자 하는 데이터와, 다음 노드의 위치 정보를 포함하고 있다. 이와 같이 연결리스트는 한 쪽 방향으로 꼬리에 꼬리를 무는 형태로 구성되어있다.
• 첫번째 노드는 헤드, 마지막 노드는 꼬리라고 부른다.
• 연결리스트를 구성하는 모든 노드들은 반드시 메모리 내에 순차적으로 저장되어 있을 필요가 없다.

• 조회: 순차적 접근 → O(N)
• 삭제, 수정: 중간에 요소를 추가하거나 삭제하는 과정에서 재정렬 불필요. (다음 노드 위치 정보만 수정하면 되기 때문) → O(1)

 

⇒ 위의 예시는 싱글 연결 리스트 (단방향)

 

 

1️⃣ 이중 연결 리스트

양방향으로, 이전 노드의 위치 정보도 포함하고 있다.

 

 

2️⃣ 환형 연결 리스트

마지막 꼬리 노드가 첫번째 헤드 노드를 가리켜, 노드들이 원형으로 구성된 연결 리스트를 의미

( 이중 연결리스트로도 환형 연결 리스트를 구현할 수 있음. 꼬리 노드의 다음노드가 헤드노드를 가리키고, 헤드노드의 이전노드가 꼬리노드를 가리키면 됨)