연결리스트
리스트의 개념
- 리스트의 의미
- 일정한 순서의 나열
- 어떤 정의에 의해서 결정된 ‘논리적인 순서’의 나열
- 배열의 정의
- 원소의 메모리 공간의 물리적인 위치를 순서적으로 결정하는 특징
- 배열의 순서는 메모리 공간에서 저장되는 원소값의 물리적 순서
- 리스트의 의미
- 리스트의 순서는 데이터가 저장되는 물리적인 위치와 상관없이 사람들의 머릿속에 인식되는 논리적인 순서 혹은 리스트에 나타나는 원소들 간의 의미적인 순서를 의미함
- 원소들의 물리적인 저장 순서나 위치와의 관계는 무관하게 원소들 간의 논리적인 순서만 유지함
- 리스트의 구현 방법
- 포인터를 이용한 리스트의 구현 방법 : 원소값을 저장하는 공간과 다음 원소를 가리키는 위치 정보를 저장하는 공간을 함께 구현하는 방법
- 배열을 이용한 리스트의 구현 방법
배열을 이용한 리스트의 구현
- 배열의 확장
- 초기 배열 선언에서 충분히 크게 하면 어느 정도는 배열의 추가 확장을 피할 수 있겠지만, 원소를 리스트의 중간에 삽입하기 위해서는 리스트의 원소값을 하나씩 뒤로 밀어야 하는 상황이 발생함
- 배열을 이용한 리스트의 원소 삽입/삭제
- 원소를 삽입하거나 삭제하기 위해서는 해당 원소의 위치 뒤에 있는 모든 원소를 뒤로 물리거나 앞으로 당겨야만 됨
- 리스트 원소값의 이동은 원소수가 많을수록 프로그램의 수행시간을 증가시킴
- 배열을 이용한 리스트의 원소 삽입/삭제 시 발생하는 문제
- 리스트의 원소 삽입은 프로그램의 실행 중에 메모리 할당을 필요로 하는 경우도 발생시킴
- 배열을 이용한 리스트의 구현은 실제 IT 서비스 환경에서는 자주 사용되지 않고 있음
- 자료의 삽입과 삭제가 빈번히 발생하는 상황에서 리스트를 배열로 구현하는 것은 빈번한 자료 이동으로 인한 비 효율적인 컴퓨팅 성능을 유발함
포인터를 이용한 리스트의 구현
- 노드의 구조
- 노드 : 리스트의 원소값(데이터) + 다음 원소를 가리키는 정보(포인터)
- 노드는 데이터 요소(원소값)와 리스트의 다음 노드를 지시하는 포인터(주소, 링크)로 구성됨
