순서리스트

순서 리스트의 개념

1. 순서 리스트(Ordered List)

(1) 정의
① 순서리스트는 선형리스트라고도 하는데, 선형 리스트(linear list)란 어떤 순서에 의해 나열된 항목들이 유한 개 있는 데이터들의 모임으로서, 컴퓨터에서 많이 사용되는 자료구조이다.
② 리스트를 구성하는 원소 상호간에 1 : 1의 관계를 가지면서 명확한 선후 관계로 구성되는 자료구조이다.
③ 리스트를 기억공간에 저장하는 방법으로는 각 원소들을 메모리상에 연속적(배열) 또는 불연속적(연결리스트)으로 위치한다.
④ 순서리스트(ordered list)란 삽입과 삭제를 할 수 있는 순서적 자료의 집합이다.⑤ 순서리스트(ordered list)는 배열구조(연접구조와 연결리스트가 있다.

2. 연접 리스트(Dense List)
(1) 정의
① 선형 리스트가 연속적인 기억공간의 1차원 배열을 이용하여 표현되었을 때 순차리스트(sequential list)라고 한다.
② 기억장소에 자료를 물리적으로 인접하면서 연속적으로 저장시키는 리스트로, 배열구조이다.
③ 임의의 원소에 접근할 때 포인터 없이 색인번호(index number)를 사용하여 리스트의 시작주소로부터 원소들의 상대적인 위치를 계산할 수 있다.
④ 임의접근(random access)이 가능하여 직접파일에서 이용된다.

(2) 장점
① 임의의 위치에 있는 원소 값을 아주 쉽게 얻을 수 있다. 즉, 검색이 용이하다.
② 리스트구조에서 1번째 원소의 값을 수정하는 연산이 많이 일어날 경우 이 리스트를 연결리스트로 구현하는 것보다 배열로 구현하는 것이 좋다.
고정된 수의 자료를 저장할 경우 기억공간 이용이 효율적이다.기록밀도가 높다

(3) 단점
① 원소 삽입과 삭제 시 이동(repacking)시간이 많이 필요하다.
② 컴파일러가 기억장소를 정적(Static) 배당하므로 기억장소 사용 효율성이 떨어진다.
③ 물리적으로 연속된 기억공간을 필요로 하므로, 외부 단편화(fragmentation)가 발생한다.

3. 연결리스트(Linked List)

(1) 정의
① 연접리스트의 문제점인 삽입과 삭제가 쉽도록 고안된 자료구조로, 삽입과 삭제가 빈번한 작업에 적합하다.
② 연결리스트는 노드(Node)를 크게 데이터 필드와 링크 필드로 나누어 다음 노드가 기억된 공간의 주소를 이전 노드의 링크 필드에 기억시키는 방식으로 모든 노드들을 하나의 리스트로 연결한다.
③ 연결리스트는 논리적 데이터 순서와 물리적 데이터 순서가 동일하지 않으므로 후속 데이터 액세스를 위해서는 포인터가 필요하다.
④ 노드들은 논리적으로는 순차적으로, 물리적으로는 비순차적으로 저장한다.

(2) 구조
① 각 노드(node)는 데이터 필드와 링크 필드(포인터)로 구성된다.
② 연결리스트는 첫 번째 노드를 가리키는 포인터가 필요하며 이를 헤드(head)라 한다.
③ 링크 필드 에는 다음 노드가 기억된 주소(포인터)가 수록된다.
④ 포인터가 다음 노드를 가리키는 구조로, 전체 노드는 서로 연결된 상태가 된다.
⑤ 각 노드는 기억장소에서 서로 이웃해 있지 않아도 된다.
⑥ 가리키는 노드가 없는 노드의 포인터를 nil(또는 null)이라 한다.