5-1 연결리스트

01. 리스트의 개념 

 

- '일정한 순서'의 나열 (배열은 물리적 순서 = 논리적 순서 동일)

- 어떤 정의에 의해서 결정된 '논리적 순서'의 나열

- 리스트의 '순서'는 데이터가 저장되는 물리적인 위치와 상관없이 사람들의 머릿속에

인식되는 '논리적인 순서', 혹은 리스트에 나타나는 원소들 간의 '의미적인 순서'를 의미함

- 물품이나 사람의 이름 따위를 일정한 순서로 적어 놓은 것

 

리스트의 의미

- 배열은 인덱스로 표현되는 '순서'가 배열 원소의 메모리 공간(주기억 장치, DDR0에서의

물리적인 위치를 의미함

- 하지만 리스트의 '순서' 개념은 어떤 정의에 의해서 결정된 '논리적인 순서'임

- 원소들의 물리적인 저장 순서나 위치와는 무관하게 원소들 간의 논리적인 순서만 유지

 

- 포인터를 이용한 리스트의 구현 방법 : 원소값을 저장하는 공간과 다음 원소를 가리키는

위치 정보를 저장하는 공간을 함께 구현하는 방법

- 배열을 이용한 리스트의 구현 방법

 

 

02. 배열을 이용한 리스트의 구현

- 구현해야 할 리스트를 3.1운동(1919년), 대한독립(1945년), 6.25전쟁(1950년), 

서울 올림픽(1988년)의 순서라고 정의한다면,

 

- 배열의 확장 : 초기 배열 선언에서 충분히 크게 하면 어느 정도는 배열의 추가 확장을

피할 수 있겠지만, 원소를 리스트의 중간에 삽입하기 위해서는 리스트의 원소값을 하나씩

뒤로 밀어야 하는 상황이 발생함

 

-  ‘배열로 구현된 리스트’는 원소의 순서가 연속적인 물리적 주소에 저장됨

 -> 원소를 삽입하거나 삭제하기 위해서는 해당 원소의 위치 뒤에 있는 모든 원소를

뒤로 물리거나 앞으로 당겨야만 됨

 -> 리스트 원소값의 이동은 원소수가 많을수록 프로그램의 수행시간을 증가시킴

 

 

배열을 이용한 리스트의 원소 삽입/삭제 시 발생하는 문제

- 리스트의 원소 삽입은 프로그램의 실행 중에 메모리 할당을 필요로 하는 경우도 발생시킴

- 배열을 이용한 리스트의 구현은 실제 IT서비스 환경에서는 자주 사용되지 않고 있음

- 자료의 삽입과 삭제가 빈번히 발생하는 상황에서 리스트를 배열로 구현하는 것은 빈번한

자료 이동으로 인한 비효율적인 컴퓨팅 성능을 유발함