[자료구조] 배열과 링크드 리스트

배열의 장단점

• 장점
  • 표현이 간단함
  • 원소의 접근 빠름
  • 빠른 임의 접근 가능
• 단점
  • 순차적으로만 표현 가능
  • 자료이동의 시간이 많이 걸림
  • 자료 크기가 미리 정의되어야 함 → overflow 발생 가능성
  • 메모리 내 저장 공간 전체가 한번에 할당 및 한번에 회수

Linked List

☑️ 구조

• Node : <data, link> 쌍의 구조
  • data : 리스트의 원소, 즉 데이터 값을 저장
  • link : 노드의 주소 값을 저장

☑️ 특징

• Linked list 내 모든 element를 “node” 라고 함
• node의 물리적 순서가 리스트의 논리적 순서와 일치하지 않음
  • element가 메모리 임의의 위치에 저장됨
• 각 node는 다음 node에 대한 주소도 함께 저장해야 함
• 노드 삽입, 삭제 비용 감소함
  • ⚠️ link를 추가로 정의해야 해서 메모리 비용 증가

☑️ 표현

• link에는 다음 node 주소 값이 들어있음
• 연결 리스트의 마지막 노드의 링크 값으로 null 저장
• 연결 리스트 전체는 포인터 변수 head로 나타냄
• head에는 리스트 첫 번째 노드의 주소가 저장됨
  • head = 리스트의 이름
  • head = null 의 경우, 공백리스트를 의미
• 노드의 필드 선택은 점 연산자 를 이용
  • ex. head.link.data = 10
  • ex. head.link = node1의 주소
• 포인터 변수에 대한 연산은 제한되어 있음
  • p = null or p != null: p의 포인터 값이 null 인가 검사
  • p = q : 포인터 p와 q가 같은 노드 주소를 가리키는지 검사
  • p ← null : p의 포인터 값으로 null 지정
  • p ← q : q가 가리키는 노드를 p도 똑같이 가리키도록 지정
  • p.link ← q : p가 가리키는 노드의 링크 필드에 q의 포인터 값을 지정
  • p ← q.link : p가 가리키는 노드의 링크 값을 p 포인터 값으로 지정