[DataStructure] 배열과 연결 리스트

[배열]

배열

• 배열 : 일정한 메모리 공간을 차지하는 여러 요소들이 순차적으로 나열된 자료구조
• 각 요소는 0부터 시작하는 고유한 순서 번호인 인덱스를 매김
• 인덱스가 주어졌을 때 특정 요소에 접근하는 연산 : O(1)
• 서로 다른 N개의 데이터에서 특정 데이터를 찾는 연산 : O(N)
• 특정 인덱스의 요소를 추가하는 연산 : O(N)
• 특정 인덱스의 요소를 삭제하는 연산 : O(N)

정적 배열

• 프로그램을 실행하기 전 크기가 고정되어 있는 배열
• 프로그램 도중 변경 X

동적 배열

• 실행 과정에서 크기가 변할 수 있는 배열
• 배열의 크기를 알기 어려운 경우, 유연하게 요소 개수를 조정해야 하는 경우 사용
• 동적 배열을 벡터라는 이름으로 구현한 프로그래밍 언어도 존재

---

[연결 리스트]

연결 리스트

• 노드 : 데이터와 다음 노드의 위치(메모리 상의 주소) 정보를 포함하는 연결 리스트 구성 단위
• 연결 리스트(Linked list) : 노드의 모음으로 구성된 자료구조
• 모든 노드들이 한 쪽 방향으로 꼬리에 꼬리를 무는 형태로 구성
  • 첫 번째 노드 : 헤드(Head)
  • 마지막 노드 : 꼬리(Tail)
• 연속적으로 구성되어 있는 데이터를 불연속적으로 저장할 때 유용
• 연결 리스트에서 특정 요소에 접근하는 연산 : O(N) → 순차적 접근이 필요하기 때문
• 새로운 요소 추가 및 삭제 연산 : O(1) → 재정렬이 불필요하기 때문

싱글 연결 리스트

• 싱글 연결 리스트(singly linked list) : 노드 내에 다음 노드의 위치 정보가 저장되어, 한 쪽 방향으로 꼬리에 꼬리를 무는 형태 (단방향 탐색만 가능)
• 단점
  • 특정 노드를 통해 다음 노드 위치 확인 가능
  • 이전 노드 위치 알기 어려움

이중 연결 리스트

• 이중 연결 리스트(doubly linked list) : 노드 내에 다음 노드의 위치 정보뿐만 아니라 이전 노드의 위치 정보도 포함하고 있는 형태 (양방향 탐색 가능)
• 장점
  • 싱글 연결 리스트 탐색 성능 완화
• 단점
  • 한 노드에 2개의 위치 정보(메모리 주소)를 저장 → 저장 공간 필요 多

환형 연결 리스트

• 환형 연결 리스트(circular linked list) : 꼬리 노드가 헤드 노드를 가리켜 노드들이 원형으로 구성된 형태

• 환형 연결 리스트는 원형 연결 리스트 라고도 부름

• 이중 연결 리스트로도 구현 가능
  

• 모든 노드 데이터 여러 차례 순회할 때 유용

---

💡 참고 자료

• Singly Linked List
• Doubly Linked List
• Circular Linked List