배열과 연결리스트

배열 Array

• 배열은 가장 기본적인 자료 구조, 같은 데이터 유형을 가진 자료들의 그룹/세트
• 연속된 기억장소를 배정받는다.
• 배열명/원소/인덱스 존재

배열은 원소를 추가/삭제하기가 어렵다. 이는 연결리스트로 해결 가능하다.

---

리스트

• 차례대로 나열된 자료들의 모임
• 나열 순서가 중요한 경우도 있음(선형리스트)
• 사용 예시: 자료 검색, 전체 검색/순회/출력, 순서 변경, 전체 목록 개수 계산, 자료 추가/삭제/변경, 빈 목록 여부 판단

---

선형리스트

• 순서대로 나열된 동일 유형의 항목들(<-> 집합: 항목간 순서 개념 X)
• 선형리스트의 예시
  요일(일,월,화,...,토)
  자음(ㄱ,ㄴ,ㄷ,...,ㅎ)
  휴대폰 문자 메시지 리스트
• C++의 경우 나열형 자료형 enum 제공
  enum Day{SUN, MON, TUE, WED, THU, FRI, SAT}
• 배열 혹은 연결리스트로 구현
• 배열로 구현한 선형리스트
  한계점: 1차원 배열에 항목들을 순서대로 저장하여 삽입 연산과 삭제 연산 시 불편함.
  

  

  
  

  

  
  => 새로운 자료구조 필요: 연결리스트(linked list)

---

연결리스트

• 자료들을 하나씩 차례대로 연결하는 방식의 자료구조
  배열의 단점들을 보완/개선
  자료 이외에 다음 자료를 가리킬 주소(포인터) 필요
• 각 자료와 포인터 정보 쌍을 노드(node)라고 지칭
  노드 = <데이터(자료), 링크(포인터)>
  데이터 필드: 자료의 원래 값(data) 저장
  링크 필드: 다음 노드의 주소값(포인터) 저장
• 연결리스트의 종류
  단일/단순 연결리스트
  이중 연결리스트
  원형 연결리스트
  etc 자신만의 연결리스트 구성 가능
• 장점
  삽입/삭제 용이, 연속된 메모리 공간 불필요, 원소 개수 유동적
• 단점
  링크 정보가 추가로 필요, 구현이 어려움, 포인터 사용으로 오류 발생 가능, 동적 메모리 할당 필요

---

배열과 연결리스트 비교

• 배열
  구현 용이
  연속된 기억장소
  삽입/삭제 제약
  원소 개수 고정
• 연결리스트
  구현 복잡(포인터 사용)
  임의의 기억장소
  삽입/삭제 용이
  원소 개수 유동적