[자료구조 이론] 선형리스트 · 순차리스트 / 연결리스트

자료구조에서 리스트는 구현방법에 따라서 크게 두가지로 나뉜다.

1) 순차(선형) 리스트 : 배열을 기반으로 구현된 리스트

2) 연결리스트 : 메모리 동적 할당을 기반으로 구현된 리스트 

 

1. 선형리스트 (Linear List) · 순차 리스트(Ordered List)

프로그래밍으로 선형리스트를 표현하고자 한다면! <인덱스 , 데이터>로 구성 된 배열 'Array'를 사용

 

- 리스트에 나열한 데이터들이 일정한 순서를 가지고 있다. 

- 우리가 표현하는 논리적인 순서와 실제 메모리상에 저장되는 물리적인 순서가 동일하다.

- 구현이 비교적 간단하고, 인덱스를 사용하여 랜덤 액세스가 가능하나 삽입, 삭제가 되는 경우에는 순서를 다시 갱신해줘야 하기 때문에 데이터의 이동이 필요하여 오버헤드(overhead)가 발생할 수 있다.

- 신규데이터의 삽입 , 삭제가 자주 발생하지 않고 삽입할 데이터가 순서가 정해져 있다면 선형리스트로 구현할 시 좋다.

 

2. 연결리스트(Linked list)

- 각노드에 저장된 다음 노드의 주소에 의해 연결되어 있다. 

- 메모리가 연속될 주소일 필요가 없어 순차리스트와 달리 물리적인 순서를 맞추기 위한 오버헤드가 발생하지 않는다.

- 원하는 만큼 노드를 동적으로 삽입,삭제를 할 수 있다.

- 단점은 순차리스트와 달리 메모리 공간에 정렬되어 있지 않고 사방에 흩어져 있어 배열의 인덱스 처럼 특정 노드에 바로 접근 할 수 어렵다. (ex. 1~20 번 까지의 노드가 있는데 8번노드에 접근하고 싶다면 1번부터 8번까지 탐색을 해야함)

연결리스트는 단일 연결 리스트(단방향)와 원형 연결리스트(양방향)로 나눌수 있다.

+이중 연결리스트까지

 

<단일연결리스트>

<단일연결리스트의 구조>

첫노드가 다음 노드를 가르키고, 다음 노드가 또 그다음 노드를 가르키며 쭉 이어나간다.

첫번째 노드는 Head노드, 마지막 노드는 Tail 노드라고 부른다. 머리와 꼬리 , 처음과 끝!

 

하나의 노드는 기본적으로 데이터필드(데이터를 저장할 공간)과 링크필드(주소를 저장할 공간) 2개로 나뉜다.

 

단일 연결리스트는 이전노드의 주소를 저장하지 않는다! Head ->Tail 처음에서 끝 방향으로만 데이터를 저장한다.

그렇다면 마지막 노드(Tail)의 링크 필드는 NULL이다.

(Head <->Tail 이건 양뱡향이겠쥬?)

 

-삽입

1. 선행자의 링크필드에 저장된 주소를 삽일할 노드의 링크 필드에 저장

2. 선행자의 링크 필드에 삽입할 노드의 주소를 저장

=> 예외처리 : 선행자를 찾을 수 없는 경우

 

-삭제 

1. 삭제할 노드의 링크필드에 저장된 주소를 선행자의 링크필드에 저장

2. 삭제할 노드를 삭제

=>예외처리 : 삭제할 노드를 찾을 수 없는 경우

 

-검색 

1. Head 부터 탐색

2. 노드의 링크 필드가 NULL 일때 까지 탐색

3. 노드의 데이터 필드가 검색 데이터와 동일 하면 탐색 중지

4. 해당데이터의 노드를 return

=>예외처리 : 검색한 데이터가 리스트에 존재하지 않는 경우

 

<원형 연결 리스트>

<원형 연결리스트 구조>

 원형 연결리스트는 단일 연결리스트나 이중 연결리스트에서 끝을 처음과 연결된 리스트를 말한다. 그림 상으로는 원으로 그렸지만 실제로는 선형 연결리스트의 마지막 노드의 next 포인터를 처음으로 연결 시켜주면 된다.

 

 원형리스트(단일 연결리스트로 표현)는 모든 포인터가 다음 노드로 연결되어있다. 이러한 cycle 구조자료의 구현이 필요할 때는 원형리스트가 유용하다. 다시 마지막에서 첫번째로 이동하지 않아도 다음 노드가 첫번째 노드를 가리키기 때문이다. 

 

- 마지막 노드(Tail)의 링크필드에 Head의 주소를 저장

- 리스트의 맨앞에 노드를 삽입하는 경우, Tail의 링크 필드를 갱신해야함!

 

 

 

단일 연결 리스트나 원형 연결 리스트는 이전 노드에 접근하기 위해선 리스트를 한 번 순회 해야한다.

=> 이점을 보완 하여, 이전 노드의 주소를 저장 한 것이 이중 연결 리스트!

 

<이중 연결리스트>

<이중 연결리스트 구조>

 이중 연결리스트란 이중 방향(포인터)를 가진 리스트를 말한다. 이 전의 단일 연결리스트는 특정 방향의 포인터 1개였지만 이중은 이전 노드, 다음 노드를 둘다 가리키는 포인터를 가지고 있다. 때문에 양쪽으로 탐색이 가능하다는 장점이있다.  

 

- 링크 필드를 두개 가지고 있다.

- Left Link Feild : 이전 노드의 주소 저장, Right Link Feild : 다음 노드의 주소 저장