[자료구조] 4. 순차 리스트

1. 리스트

1) 리스트(list)

• 가장 일반적으로 사용되는 데이터 구조로, 관련된 자료들이 일정한 순서로 나열됨

• 비슷한 특성을 가진 자료들을 연결해 놓은 구조

• 배열도 리스트의 일종으로 볼 수 있음

• 학생 명단, 은행 고객 명단, 월별 판매액 등 다양한 분야에서 활용됨

 

배열을 이용한 리스트

• 구현이 간단하지만 삽입·삭제 시 오버헤드 발생

• 항목 개수 제한 존재

 

연결 리스트를 이용한 리스트

• 구현이 복잡하지만 삽입·삭제가 효율적

• 크기 제한 없음

 

 

2. 순차 리스트

1) 순차 자료구조의 개념

• 데이터를 논리적 순서대로 메모리에 연속 저장하는 방식

• 논리적 순서와 물리적 순서가 일치해야 함

• C 프로그래밍에서는 배열을 이용해 구현

 

순차 자료구조 vs. 연결 자료구조

순차 자료구조

• 데이터를 연속된 메모리 공간에 저장

• 삽입·삭제 후에도 자료가 연속적으로 저장됨

• 배열을 이용해 구현

 

연결 자료구조

• 데이터가 물리적 순서와 상관없이 링크를 통해 연결됨

• 삽입·삭제 시 링크만 변경되며 물리적 순서는 변하지 않음

• 포인터를 이용해 구현

 

2) 순차 리스트

• 순서를 갖는 리스트로, 간단하고 일반적인 자료구조

• 원소들이 연속된 기억장치에 저장됨

• 배열을 이용해 구현 가능

• 모든 자료구조의 형태는 여러 종류의 리스트로 볼 수 있음

• 문자 스트링, 배열, 파일 등도 리스트의 한 예시

 

3) 순차 리스트 표현을 위한 데이터 구조

배열

• 가장 보편적인 데이터 구조

• 리스트 원소는 배열의 인덱스로 접근 가능

• 삽입·삭제 시 연속적인 구조 때문에 비효율적

 

연결 리스트

• 포인터를 사용해 리스트 원소 간의 순서 유지

• 삽입·삭제 연산이 쉽지만 임의 원소 검색은 어려움

• 사용 목적에 따라 배열과 연결 리스트 중 선택

 

4) 리스트 표현 형식

• 리스트 이름 = (원소1, 원소2, ..., 원소n)

• 공백 리스트: ( )

• 예시: 학생 리스트 = (나수연, 김솔희, 손필수, 박지성, 노혜숙)

 

5) 순차 리스트의 삽입과 삭제

원소 삽입 방법

• 삽입할 자리 이후의 원소들을 한 칸 뒤로 이동 후 삽입

 

원소 삭제 방법

• 삭제 후 이후 원소들을 한 칸 앞으로 이동

 

순차 리스트의 특징

• 인덱스를 사용해 특정 원소에 쉽게 접근 가능

• 삽입·삭제 시 원소 이동으로 인해 오버헤드 발생

• 삽입·삭제가 많은 경우 비효율적 → 연결 리스트 사용 권장

---

이 내용은 휴넷사회복지평생교육원의 자료구조 강의를 듣고 정리한 것입니다.