swift로 구현한 연결리스트(Linked List)

[특징]

1. 다음 노드에 대한 참조를 가진 형태의 데이터 구조이다. 배열과 유사한 데이터 구조를 가지고 있지만 배열은 일정 규모의 연속된 메모리 범위를 할당받아야 하는 반면, 연결리스트는 그렇지 않다는 차이점이 있다. 보통 스택이나 큐 등 다른 구조를 구현하는 데 사용한다. 스택과 큐를 구현할 때 배열 대신 연결리스트를 사용할 수 있다.

2. 종류

 - 단일 연결 리스트(Singly linked list) : 자료 공간 1개와 다음 노드를 가리키는 포인터로 구성된 노드를 가지는 연결 리스트

 - 이중 연결 리스트(Doubly linked list) : 앞의 노드와 뒤의 노드를 가리키는 포인터가 2개 있는 연결 리스트

 - 순환 연결 목록(Circular linked list) : 마지막 노드와 처음 노드가 연결되어 원형 구조를 이루고 있는 연결 리스트

3. 장/단점 

 - 장점 : 데이터 삽입과 삭제가 빈번하게 일어나는 경우, 데이터 규모가 무척 큰 경우 사용할 수 있다.

 - 단점 : 연결리스트의 각 노두는 서로 연속된 메모리를 할당받지 않으므로, 연결 리스트의 구조를 미리 최적화하여 관리하지 않을 경우 리스트 인덱싱 성능이 낮게 유지될 수 있다. 또한 노드 관리에 일정량의 메모리가 소진된다.

 

 

여기서는 단일 연결 리스트와 이중 연결 리스트를 구현해 보도록 하겠다.

먼저, 이전에 배열로 구현한 스택을 단일연결리스트로 구현해 보자

 

1) 노드 구현

노드는 연결리스트에 저장되는 1개의 데이터 단위라고 보면 된다.

데이터 값을 저장하는 data변수와 그 다음 노드를 가리키는 포인터 역할을 하는 next로 구성되어 있다.

 

 

2) 연결리스트로 스택 구현

프로퍼티

 - head : 연결리스트의 첫번째 노드(스택이므로 가장 최근에 들어온 맨 위에 있는 데이터)

 - count : 데이터 수 반환

메소드

 - push(element:) : 스택에 데이터 추가

 - isEmpty() : 스택이 비어있는 지 확인

 - pop() : 가장 위의 값(최근 값) 삭제 및 반환

 - peek() : 가장 위의 값(최근 값) 반환(삭제X)

 

위의 프로퍼티와 메소드를 가지고 있는 연결리스트 구조체를 구현하면 아래와 같다.

 

 

 

3) 사용편의를 위한 프로토콜 추가

아래 프로토콜에 대한 보다 자세한 설명은 이전 게시물인 Stack을 참고하면 된다.

 

 

 

다음으로 이중연결리스트(Doubly Linked List)를 구현해보자

 

1) 노드 구현

단일연결리스트와 다른 점은 이전 노드를 가리키는 previous 포인터를 하나 더 가진다는 것이다.

 

 

2) 이중연결리스트 구현

프로퍼티

 - head : 첫 번째 노드

 - tail : 가장 마지막 노드

 - isEmpty : 이중연결리스트가 비어있는 지 확인

 - count : 저장된 데이터 수 반환

메소드

 - append(node:) : 새로운 데이터 추가

 - insert(node:, at:) : 원하는 인덱스에 새로운 데이터 추가

 - node(at:) : 인덱스 번호로 원하는 node 반환

 - node(by:) : 값으로 원하는 node 반환

 - remove(at:) : 인덱스 번호로 원하는 node 삭제

 - remove(by:) : 값으로 원하는 node 삭제

 - removeAll() : 모든 노드 삭제

 - scanValues() : 저장된 모든 값 출력

 

위의 프로퍼티와 메소드를 가지고 있는 이중연결리스트 클래스를 구현하면 아래와 같다.