자료를 저장하는 방법 중 크게 배열과 연결리스트가 있습니다.
그럼 언제 배열을 사용하고 언제 연결리스트를 쓸까요? 먼저 두 자료구조의 장, 단점에 대해 알아보겠습니다.
표1 배열, 연결리스트 장점 및 단점
배열은 접근이 빠르고 간단합니다. n번째 인덱스에 접근할 경우 arr[n]을 사용하면 빠른 시간에 접근할 수 있습니다.
그러나 배열을 사용하기 위해서는 처음에 배열의 크기를 선언해야 하고 크기의 수정이 불가능하기 때문에 메모리 사용이 비효율적입니다.
또한 중간 데이터를 삭제 했을때 빈 배열을 처리하는 것이 번거롭습니다..( 자료구조를 공부해보신 분이라면 이해하실 겁니다ㅠ)
그러나 연결리스트는 위의 단점을 해결할 수 있습니다.
필요할때마다 데이터를 생성하여 연결하면 되기 때문에 메모리를 효율적으로 사용가능합니다. 그러므로 삭제 및 추가를 할때 데이터 재구성이 용이합니다.
그러나 탐색이 느립니다. 첫번째 혹은 마지막 노드를 탐색할때는 쉽게 찾을 수 있지만, 중간 노드를 탐색할 경우 첫노드부터 순차적으로 탐색해야 하기 때문에
느리고 구현이 까다롭습니다. (이 부분에 관한 설명은 아래에서 자세히 설명하겠습니다)
또한 데이터를 저장할 공간 뿐만 아니라, 다음 노드의 주소를 저장하는 공간이 추가적으로 필요하다는 단점이 있습니다.
연결리스트를 처음 접하신 분들은 이 설명이 잘 이해안될수 있습니다. 아래에서 더 자세히 설명하겠습니다.
노드(Node)
연결리스트는 '노드' 라는 객체로 이루어져 있습니다.
그림1 Node 구성
위 그림과 같이 Data를 저장할 공간과 다음 주소를 가리킬 공간이 필요합니다. 사용자가 입력하는 정보를 DATA영역에 담고 노드가 추가될 때마다 Next address를 이용하여 다음 노드와 연결합니다.
코드로 나타내면 아래와 같이 구조체로 구현할 수 있습니다
typedef struct Node{ int data; Node *next; }Node;
전체적인 연결리스트 구조는 아래와 같이 나타낼 수 있습니다.
그림2. 연결리스트 구조
이와 같이 각 노드는 연속된 공간에 저장되어 있지 않고 메모리의 여러 부분에 분포되어 있습니다.
각 노드에 다음 노드의 주소를 저장함으로써 다음 노트를 탐색할 수 있습니다. 다음 주소를 가리켜야 하기 때문에 포인터를 이용해 구현할 수 있습니다.
그러면 마지막 노드는 어떻게 알 수 있을까요?
노드가 가리키는 다음 주소가 NULL이면 이 노드는 마지막 노드라고 할 수 있습니다.
연결리스트 구현
연결리스트를 구현하기 위해서는 다음과 같은 함수를 구현해야 합니다.
초기화(init) / 삽입(Insert) / 삭제(Remove)
초기화
위에서 설명한 노드를 생성하는 과정입니다.
노드를 접근하기 위해서는 맨 처음 노드의 주소를 가리킬 노드가 필요합니다. 이 노드를 head라고 표현하겠습니다.
또한 나중에 구현할 삽입의 시간복잡도를 줄이기 위해 마지막 노드를 가리키는 노드 tail을 하나 만들겠습니다. (삽입 기능 구현에서 자세히 설명하겠습니다)
초기화하는 과정에서 다음 주소를 가리키는 포인터는 null로 설정합니다. null은 '가리키는 노드가 없음' 을 의미합니다.
초기화 코드는 아래와 같습니다.
void init(){ head = new Node; tail = new Node; head->next = NULL; tail->next = NULL; }
삽입
다음과 같은 연결리스트가 있을 때 새로운 노드를 추가하는 방법에 대해 알아보겠습니다.
삽입을 구현하는 방법은 세가지 방법으로 나뉠 수 있습니다.
1) 맨 앞에 삽입하는 방법
맨 앞에 노드를 추가하는 경우
새로 추가되는 노드의 다음주소 --> 현재 head가 가리키는 주소
head가 가리키는 주소 --> 새로 추가된 노드
이렇게 추가할 수 있습니다. 그림으로 나타내면 아래와 같습니다.
구현은 1번 방법으로 하겠습니다. 코드는 아래와 같이 나타낼 수 있습니다.
void Addnode(int data){ //추가할 노드 만들기 Node *NewNode = new Node; NewNode->data = data; NewNode->next = NULL; //노드가 하나도 없으면 head에 연결하기 if(head->next == NULL){ head->next = NewNode; } else{ //새로 추가되는 노드의 다음주소 --> 현재 head가 가리키는 주소 NewNode->next = head->next; //head가 가리키는 주소 --> 새로 추가된 노드 head->next = NewNode; } }
2) 맨 마지막에 삽입하는 방법
맨 앞에 삽입하는 경우와 거의 같습니다. head 대신 tail를 사용하면 됩니다.
여기서 tail 노드의 필요성을 알 수 있습니다. 만약 tail노드가 없다면 매번 삽입할 때마다 처음부터 끝까지 탐색해야 하는 번거로움이 발생합니다.
그래서 매번 O(n)의 시간복잡도가 발생합니다. 만약 tail노드가 있다면 O(1)의 시간복잡도로 처리할 수 있습니다!
맨 마지막에 추가하는 과정은 다음과 같습니다.
새로 추가되는 노드의 다음주소 --> Null (마지막 노드이기 떄문에)
tail이 가리키는 노드의 다음 주소 - > 새로 추가되는 노드
tail이 가리키는 주소 --> 새로 추가된 노드
그림으로 나타내면 아래와 같습니다.
3) 원하는 위치에 삽입하는 방법
먄약 2번쨰, 3번쨰자리에 추가하고 싶다! or 정렬을 하면서 추가하고 싶다!
이런 경우가 있을겁니다. 이럴 경우엔 탐색을 통해 원하는 위치를 찾고 그 위치에 새로운 노드를 추가해야합니다.
위 예제에서 2번째노드(4)와 3번째노드(1) 사이에 추가한다고 가정해봅시다.
우선 삽입할 위치를 찾는 노드 cur (current)가 필요합니다.
위 두 가지 경우에선 head, tail과 같은 위치는 담고 있는 노드가 있었지만, 이번 경우엔 직접 설정해야만 합니다!
다음과 같은 과정을 통해 노드를 추가할 수 있습니다.
1. 탐색을 통해 cur노드가 4를 가리키게 만듭니다.
2. 새로운 노드 5가 가리키는 주소 --> cur이 가리키는 노드4가 가리키는 다음 노드(1)
3. cur이 가리키는 노드4가 가리키는 다음노드 --> 새로운 노드 5
삭제
노드의 삭제는 '원하는 자리에 삽입' 하는 과정과 유사합니다.
그러나 삭제할 노드의 전과 삭제할 노드의 후를 연결해줘야 하기 때문에 또 하나의 노드가 필요합니다.
이 노드를 pre라고 표현하겠습니다. 이해를 돕기 위해 그림을 먼저 살펴보겠습니다.
삭제할 노드를 1 이라고 가정하겠습니다.
1. 탐색을 통해 삭제할 노드를 cur이 가리키게 하고 , 삭제할 노드의 바로 전 노드를 pre가 가리키게 합니다.
2. pre가 가리키는 노드의 다음 주소 --> cur이 가리키는 다음 주소
3. cur이 가리키는 노드는 free합니다.
구현된 코드는 아래와 같습니다.
void RemoveNode(int remove_data){ Node *cur = head->next; Node *pre = head; //탐색을 통해 삭제할 노드를 cur이 가리키게 하고 //삭제할 노드의 바로 전 노드를 pre가 가리키게 합니다. while(cur->data != remove_data){ pre = cur; cur = cur->next; } //pre가 가리키느 노드의 다음 주소 --> cur이 가리키는 다음 주소 pre->next = cur->next; //cur이 가리키는 노드 free free(cur); free(pre); }
전체 소스코드는 아래 주소에서 확인하실 수 있습니다
[https://github.com/choseungyoon/Algorithm/blob/master/DataStructure/Simple_Linked_list.cpp]
위에서 설명된 연결리스트는 단순연결리스트 입니다. 쉽지 않죠..?
한번에 이해 안될 수도 있고, 저의 설명이 부족한 부분도 있을겁니다.
이해가 안되시는 부분이나 설명이 잘못된 부분이 있다면 댓글을 통해 알려주세요!!
그리고 연결리스트는 원형, 양방향리스트와 같이 여러 종류가 있습니다.
다음 시간엔 연결리스트의 종류에 대해 알아보겠습니다.
감사합니다!
'알고리즘 > 자료구조' 카테고리의 다른 글
| [자료구조] 스택 - Stack (0) | 2017.11.12 |
|---|---|
| 다익스트라 알고리즘(Dijkstra) (0) | 2017.10.06 |
