[자료구조] 리스트(List)

[한빛아카데미] 자바로 배우는 쉬운 자료구조 책으로 학습한 내용을 정리한 것입니다.

 

* 리스트(List) : 데이터를 나열하는 것

* 선형 리스트/순서 리스트(Linear List/Ordered List)

- 리스트에서 나열한 원소들 간에 순서를 가지고 있는 리스트

- 특징

 1) 자료들이 순서대로 연속적으로 메모리에 저장됨

 2) 삽입, 삭제 시 순서에 변함이 없음

 3) 접근 속도가 빠름

 4) 알고리즘이 간단함

 

* 순차 자료구조

- 원소들 간의 논리적인 순서와 메모리에 저장하는 물리적인 순서가 같은 구조

- 순차 자료구조에서의 i번째 위치 = 시작위치 + (i-1) * 원소의 길이

- 배열을 이용하여 구현함

- 원소 삽입/삭제 시 물리적으로 원소를 당기거나 밀어야 해서 추가적인 오버헤드 발생 -> 삽입/삭제 연산 많을 때 사용하는 것은 비효율

 

 

[선형 리스트에서의 원소 삽입]

- (n+1)개의 원소로 이루어진 선형 리스트에서 k번 자리에 원소를 삽입하려면 빈 자리를 만들기 위해 k번 원소부터 마지막 원소인 n번 원소까지 (n-k+1)개의 원소를 모두 한자리씩 뒤로 이동하여 추가하려는 원소를 삽입

- 빈 자리를 만들기 위한 이동 횟수 = (n-k+1) -> 마지막 원소의 인덱스 - 삽입할 자리의 인덱스 + 1 

출처 : https://toward-the-future.tistory.com/entry/자료구조-선형-리스트-Linear-List

 

 

[선형 리스트에서 원소 삭제]

- 선형 리스트는 논리 순서와 같은 순서대로 원소들이 메모리에 연속하여 저장되어야 하는 순차 자료구조이기 때문에 빈자리 존재하지 않음

- 원소를 삭제한 위치 이후에 있는 원소들을 모두 한자리씩 앞으로 옮겨서 빈자리를 채워줌

- (n+1)개의 원소로 이루어진 선형 리스트에서 k번 자리의 원소를 삭제했을 경우에는 (k+1)번 원소부터 마지막 n번 원소까지 (n-(k-1)+1)개의 원소를 한자리씩 앞으로 이동

- 필요한 이동 횟수 = (n-(k-1)+1) = n-k -> 마지막 원소의 인덱스 - 삽입할 자리의 인덱스

출처 : https://toward-the-future.tistory.com/entry/자료구조-선형-리스트-Linear-List