자료구조의 분류 및 리스트의 종류와 차이

자료구조

• 프로그램에서 사용하기 위한 자료를 기억장치의 공간 내에 저장하는 방법과 저장된 그룹 내에 존재하는 자료 간의 관계, 처리 방법 등을 연구 분석 하는 것

자료구조의 이용

• 정렬 - 기억장치 내의 자료를 일정한 순서에 의해 나열하는 것
• 검색 - 기억장치 내의 자료를 찾는 것
• 파일 편성 - 자료를 기억 매체에 저장할 때의 파일 구조
• 인덱스 - 파일에서 특정 자료를 빠르게 찾기 위한 색인표

자료구조의 분류와 차이점

• 선형 자료구조
  • 스택, 큐, 리스트(선형리스트, 연결리스트), 데크
• 비선형 자료구조
  • 트리, 그래프

선형 리스트와 연결 리스트의 차이

• 둘다 순서가 존재하는 리스트 자료형이지만 차이가 있다.
• 선형리스트는 기억 장치 내에 연속적으로 메모리 주소 공간을 가지므로 포인터 연산처럼 인덱스로 접근하기가 용이하지만 삽입과 삭제가 어렵다.
  • 자료들을 연속적인 기억장소에 저장된 리스트, 임의의 노드에 접근할 때는 인덱스를 사용하므로 포인터가 없음
• 연결리스트는 기억 장치 내에 비연속적인 메모리 주소 공간을 가지지므로 포인터를 통해 다음 자료의 주소 공간을 가리키므로 탐색이 쉽지 않지만 삽입과 삭제가 용이하다.
  • 자료들을 임의의 기억공간에 저장시키고, 자료 항목의순서에 다라 노드의 포인터 부분을 이용하여 서로 연결시킨 자료구조
  • 희소행렬(행렬의 요소들 중에 많은 부분이 0으로 되어 있는 행렬)을 연결 리스트로 표션 시 기억장소의 이용 효율이 좋음