배열의 단점인 추가와 삭제 시 메모리의 비효율성과 번거로움을 보완하기 위해 연결리스트를 알고 있으면 유용합니다.
연결리스트란?
연결리스트에는 단순 연결리스트, 이중 연결리스트, 원형 연결리스트가 있다.
이번에는 단순 연결리스트에 대해서만 알아보겠습니다.
장점
- 필요한 경우 데이터를 생성하여 연결한다. --> 메모리 효율성↑
- 추가 및 삭제 시 데이터 재구성이 용이하다.
단점
- read가 느리다. --> 중간에 있는 노드 탐색 시에는 순차적으로 탐색을 해야한다.
- 데이터 저장 공간과 더불어 다음 노드의 주소를 저장할 공간이 추가적으로 필요하다.
노드란?
| DATA | next address |
|---|
이런 모습을 가졌는데, DATA에는 사용자가 입력하는 정보를 담고 노드가 추가될 때마다 Next address를 이용하여 다음 노드와 연결한다.
typedef struct Node{
int data;
Node *next;
}Node;코드로는 이렇게 나타낸다.
각 노드는 메모리의 여러 부분에 분포되어 있다.
각 노드에 다음 노드의 주소를 저장함으로써 다음 노트를 탐색하는 방식이다.
노드가 가리키는 다음 주소가 NULL이면 이 노드는 마지막 노드이다.
*null은 가리키는 노드가 없다는 뜻
연결리스트를 구현하는 법
1. 초기화(init) - 노드 생성 과정
(노드를 생성하려면 맨 처음 노드의 주소를 가리킬 노드가 필요합니다. 이 노드를 head, 마지막 노드를 가리키는 노드 tail이라고 설정하겠습니다.)
void init(){
head = new Node;
tail = new Node;
head->next = NULL;
tail->next = NULL;
}이는 초기화를 위한 코드.
맨 처음과 마지막 노드를 NULL로 표현하여 초기화 시켜준다.
2. 삽입(Insert) - 새로운 노드 추가 시
-
맨 앞에 삽입
새로 추가되는 노드의 다음주소 --> 현재 head가 가리키는 주소,
head가 가리키는 주소 --> 새로 추가된 노드
새치기를 생각하면 편하다. -
맨 마지막에 삽입
맨 앞에 삽입하는 방법이랑 비슷하다.
head 대신 tail를 사용하면 된다.
여기서 tail 노드의 중요성이 발견된다.
만약 tail노드가 없다면 매번 삽입할 때마다 처음부터 끝까지 탐색해야 하는 번거로움이 발생하기 때문!
tail노드가 없으면 O(N)의 시간복잡도로 번거롭지만,
tail노드가 있다면 O(1)의 시간복잡도로 처리되어 간단해진다.
새로 추가되는 노드의 다음주소 --> Null (마지막 노드이기 떄문에),
tail이 가리키는 노드의 다음 주소 - > 새로 추가되는 노드,
tail이 가리키는 주소 --> 새로 추가된 노드 -
원하는 위치에 삽입
먼저 삽입할 위치를 찾는 노드 cur (current)가 필요하다.
2번째 노드와 3번째 노드 사이에 새로운 노드를 삽입한다고 가정해봅시다.
1. 탐색을 통해 cur노드가 2번째 노드를 가리키게 한다.
2. 새로운 노드가 가리키는 주소 --> (cur이 가리키는)2번째 노드가 가리키는 다음 노드(3번째 노드)
3. (cur이 가리키는)2번째 노드가 가리키는 다음노드 --> 새로운 노드
3. 삭제(Remove) - 노드 삭제 방법
위 삽입 방법 중 원하는 위치에 삽입하는 방식과 비슷하다.
삭제할 노드의 전과 삭제할 노드의 후를 연결해줄 pre 노드가 필요하다.
1. 탐색을 통해 삭제할 노드를 cur이 가리키게 하고 , 삭제할 노드의 바로 전 노드를 pre가 가리키게한다.
2. pre가 가리키는 노드의 다음 주소 --> cur이 가리키는 다음 주소
3. cur이 가리키는 노드는 free로 변한다.
정리
메모리의 효율성과 데이터 재구성을 생각하면 데이터 수정을 자주 하게 될 경우에는 연결리스트를 사용해주는 것이 좋겠다.
노드를 사용하여 가리키고 다음 노드로 넘어간다는 점이 아 확실히 읽을 때는 오래 걸리겠구나 싶었다.
노드의 주소로 데이터 수정이 가능하다는 것만 이해하면 조금은 더 간단하게 느껴지지 않을까??
마치며
배열과 연결리스트를 비교하며 알아보게 되었는데, 연결리스트가 더 복잡하긴 한 것 같다. 선형구조로 시작을 했으니 다음 시간에는 선형구조 중 자주 쓰이는 큐와 스택에 대해 공부해봐야겠다!
