[자료구조] 선형 자료구조 - 선형 리스트 (연속 리스트 & 연결리스트)

List
: 나열하다

 

 

리스트란?

리스트(List) : 나열한 목록

선형 리스트(Linear List) : 원소들이 일정한 순서에 의해 나열된 자료구조

 

 

리스트 표현 방법

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

 

 

종류

연속 리스트	- 배열을 이용 - 기억 장소를 연속적으로 배정받음 → 기억 장소 이용 효율 = 밀도 1로 가장 좋음 - 중간에 데이터를 삽입하는 경우, 연속된 빈 공간 생성을 위해 삽입/삭제 시 자료의 물리적인 이동 필요 - 삽입/삭제 연산이 많이 필요한 문제에 적용할 경우 비효율적 - 원소들의 순서를 따로 표시할 필요 없이 간단히 구성 가능 - 인덱스를 사용하여 특정 원소를 쉽게 액세스 가능 - 시작 위치와 원소의 크기를 알고 있다면 특정 원소의 위치 알아낼 수 있음
연결 리스트	- 포인터를 이용 - 자료들을 임의의 공간에 기억시키고, 자료 항목의 순서에 따라 노드의 포인터를 이용하여 서로 연결시킴 - 노드의 삽입/삭제 작업 용이 - 기억 공간이 연속적으로 놓여 있지 않아도 저장 가능 - 연결을 위한 링크(포인터)필요 → 연속 리스트에 비해 기억 공간의 효율 떨어짐 - 연결을 위한 포인터를 찾는 시간 발생 → 접근 속도 느림 - 중간 노드 연결이 끊어지면 그 다음 노드를 찾기 힘듦

 

 

선형 리스트 원소 삽입/삭제

선형 리스트에 새로운 원소를 삽입하기 위해서는 원소 삽입 전에 미리 원소들을 옮겨 새로운 원소를 삽입할 자리를 만들어 준 후에 원소를 삽입해야 한다. 또한 마찬가지로 원소를 삭제하는 경우, 삭제된 원소가 있던 자리는 빈 자리가 되므로 빈 자리가 없도록 삭제한 위치 이후에 있는 원소들을 옮겨주어야 한다.

 

[선형 리스트 원소 삽입]

(n+1)개의 원소로 이루어진 선형 리스트에서 k번 자리에 원소를 삽입하는 경우,

빈 자리 생성을 위해 k번 원소부터 마지막 원소인 n번 원소까지 n-k+1개의 원소를 모두 한 자리씩 뒤로 밀어야 함.

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

 

[선형 리스트 원소 삭제]

(n+1)개의 원소로 이루어진 선형 리스트에서 k번 자리의 원소를 삭제하는 경우,

(k+1)번 원소부터 마지막 원소인 n번 원소까지 n-(k+1)+1개의 원소를 모두 한 자리씩 앞으로 옮겨야 함.

따라서 빈 자리를 없애기 위한 이동 횟수 = n-(k+1)+1 = 마지막 원소의 인덱스 - 삭제한 원소의 인덱스