오랜만에 올리는 글이네요.
평소에 전 알고리즘 관련 글은 잘 올리지 않았는데요,
(아예 안 올린 거 아닌가..?)
이유는 제가 코딩을 잘하는 편이 아니기도 하고, 알고리즘은 미숙하기 때문입니다.
이번엔 용기를 내서 알고리즘 관련 글을 써보려 합니다!
(이거 하느라 혼자서 구현해 보는데 이상한 짓 했던 건 안 비밀)
'연결리스트'인데요, 여러 종류가 있지만 그중
'이중 연결리스트(Doubly Linked List)'에 대해 다뤄보려 합니다..!
<챕터>
1. 이중 연결리스트의 기초
2. 코드를 짜기 위한 기본 개념
3. 코드
* 제가 글을 쓸 때 항상 지키는 원칙인 '초보자도 쉽게 이해하게'에 맞게 써보려 했으나 다 쓰고 보니까 많이 헷갈리실 것 같아요..ㅠ 댓글 달아주시면 도와드릴 수 있는 선에서 답변해드리겠습니다! (죄송합니다..) *
이중 연결리스트의 기초
일단 코드를 짜기 전에 어떤 구조로 되어있는지 부터 알아봅시다.
'연결리스트(Linked LIst)'는 각각의 노드(Node)를 만들고,
이를 배열처럼 연결하는 방식의 저장방법입니다.
초보자 분들을 위해 쉽게 설명해 드리자면,
배열은 각 저장 공간이 나란히 저장되어 있는 반면,
연결리스트는 여기저기에 퍼져있는 대신 서로 연결되어있습니다.
그때, 연결리스트에서 연결되어 있는 저장 공간들을 '노드'라고 부릅니다.
리스트의 제일 앞에 있는 노드를 '머리(head)'
제일 뒤에 있는 부분을 '꼬리(tail)'이라 합니다.
연결리스트 알고리즘은 이를 프로그래밍하는 겁니다.
노드와 노드끼리 연결하는 방법은 여러 가지가 있는데,
| 단일 연결리스트 | 이중 연결리스트 | 다중 연결리스트 | 원형 연결리스트 |
| 노드가 자신 앞에 있는 노드만 가리킴 | 노드가 자신의 앞, 뒤 노드를 다 가리킴 | 각 노드가 두 개 이상의 노드를 가리킴 | 마지막 노드가 제일 앞 노드를 가리킴 |
이 중 '이중 연결리스트'는 노드가 자신의 앞, 뒤 노드를 다 가리키는 방법입니다.
이해가 쉽도록 그림을 그려봤습니다. (단일 연결리스트와 비교)
그런데 이 '화살표'는 무엇을 뜻할까요?
노드끼리 연결 되어있다는 것은 알겠는데.. 어떻게 연결시키는 걸까요?
연결리스트는 '다른 노드의 주소값'을 이용하여 다른 노드를 가리킵니다.
즉, 한 노드에 다른 노드의 주소값이 저장되어 있다는 뜻이죠.
(그래서 '포인터'를 사용합니다. 포인터는 '변수의 메모리 주소를 가리키는 변수'를 뜻합니다.)
화살표는 '노드가 가리키고 있는 다른 노드'입니다.
이 노드가 어떤 노드의 주소값을 가지고 있는지 표현하는 겁니다.
기본 개념 정리
아 물론 대부분은 이해할 거라 생각하지만
아까 포인터 설명한 것처럼 아예 초보 분이 보셔도 이해되도록 작성하고 싶기 때문에!
또 기본 개념은 중요하기 때문에! 정리할 겁니다.
1. 구조체 (structure)
/*========== 형식 ==========*/
typedef struct [이름] {
[코드]
}[다른 이름(간추려 부를 이름)];구조체란, '기존 타입을 이용해 만든 새로운 타입'입니다.
사용자가 정의할 수 있으며, 밑에 예문을 보며 이해하시는 게 빠를 것 같네요!
typedef struct Human {
int hp;
int atk;
int def;
char name[5];
}human;위에서 말한 '타입'은 int, float 같은 타입들을 말하는 겁니다.
위 코드 같은 경우는 'Human'이라는 새로운 타입을 선언한 거고요,
'기존 타입을 이용해' 만들 수 있으므로, Human이라는 구조체 안에 다른 타입들로 선언된 변수들이 있습니다.
이래도 이해가 힘드실 수 있는데요, 그냥 하나의 '형식'이라 보시면 됩니다!
typedef struct Human { // 구조체
int hp; // 구조체 안 변수들은 '초기화'가 불가능!
int atk; // 즉, int i = 0; 처럼 기본 설정 불가
int def;
}human; // 굳이 넣어줄 필요는 없으나 넣는 것이 좋음
int main() {
human Mike; // int같은 'human'이라는 한 타입이기 때문에 이렇게 선언
struct Human Jane; // 이렇게도 선언 가능!
Mike.hp = 100; // 'human'이라는 묶음 안에 hp, atk, def, name이 다 같이 정의되어 있음
Mike.atk = 40; // Mike라는 변수는 그 4개를 다 가지고 있음 -> 각자 설정 가능
Mike.def = 50; // [변수 이름].[접근할 부분] 으로 각 변수 설정 가능!
Jane.hp = 100; // 만약 구조체를 포인터로 선언했다면, '.'대신'->'로 연결!
.
.
.
}위에 코드를 보면서 이해해 봅시다.
'Human'이란 구조체는 하나의 '타입'이기 때문에, int처럼 변수 선언이 가능합니다.
변수 선언을 할 시, Human안에 정의된 그 '형식'이 자연스레 변수의 형식이 됩니다.
즉, human으로 선언한 변수는 그 안에 있는 hp, atk, def를 사용할 수 있다는 것이죠.
근데 이것들을 사용하기 위해선 어떻게 해야 할까요?
human Mike;라고 했을 때, MIke = 100; 한다고 hp가 설정되진 않을 겁니다.
그건 '변수 뒤에 '.'을 붙이면' 됩니다!
물론 '.'을 붙인 뒤 사용할 변수를 이름을 붙여야 하지요.
Mike.hp = 100;
이제 됐네요!
아까 '포인터'(주소값을 가리키는 변수)를 언급했었죠?
포인터는 형식 뒤에 *을 붙여(int* a, float* b 등) 만들 수 있는데요,human도 하나의 '타입'이기 때문에 포인터로 선언이 가능합니다.
만약 포인터로 선언했을 경우, '.' 대신 '->'를 사용합니다.(이중 연결리스트에 경우 주소값에 접근을 하기 때문에 포인터로 선언합니다. 잘 기억해 두세요!)
2. 동적 변수(malloc) / 메모리 해제(free)
#include <stdlib.h> // malloc 함수가 선언되어 있는 헤더 파일
[변수 선언] = ([타입])malloc([변수 크기]);
/*====================*/
free([변수 이름]);
/*========== ex ==========*/
int i = (int)malloc(sizeof(int)); // 동적 변수 'i' 선언
free(i); // 동적변수 'i' 해체(삭제)malloc(memory allocation)은 '동적 변수를 할당하는 함수'입니다.
동적 변수란, '프로그램 실행 중 선언/해체가 가능한 변수'입니다.일반적으로 int i = 0;처럼 선언하는 변수들은 '정적 변수'로, 프로그램 실행 전 선언됩니다.(C언어 같은 컴파일 언어는, 코드를 한 줄 한 줄 실행하는 것이 아니라 기계어로 먼저 변환시킨 후 실행됩니다.)
free는 '동적 변수를 해체(삭제)할 때 쓰는 함수'입니다.
연결리스트는 일반적인 배열처럼 미리 메모리를 부여하는 것이 아닌,
실행 중 부여했다가 삭제하므로 동적 변수를 사용합니다.
(stdlib.h 헤더 파일에 선언되어 있습니다! stblib.h 선언 안 하면 오류 나요!)
3. nullptr
일단, NULL은 '메모리의 빈 공간'을 뜻하는 단어이며, 0으로 정의되어 있습니다.
#define NULL 00은 정수형이기 때문에, 포인터를 초기화시켜줄 때 사용하기에는 별로 안 좋습니다.
nullptr(null pointer value)는 '포인터를 표현하는 값 중 NULL을 표현하는 값'입니다.
포인터를 초기화 시켜줄 땐 이것을 사용하는 것이 좋죠.
연결리스트 구현
이 정도면 대충 설명을 다한 것 같네요!
이번에 프로그래밍할 부분은 이렇습니다.
1. Node 구조체 선언 및 초기화
2. 리스트 맨 앞에 노드 넣기
3. 리스트 맨 뒤에 노드 넣기
4. 원하는 부분에 노드 넣기
5. 리스트 맨 앞 노드 지우기
6. 리스트 맨 뒤 노드 지우기
7. 원하는 부분 노드 지우기
8. 리스트 출력하기
9. main함수
<전체 코드>
#include <stdio.h>
#include <stdlib.h>
typedef struct Node
{
int data;
Node* next;
Node* prev;
}node;
node* head = (node*)malloc(sizeof(node));
node* tail = (node*)malloc(sizeof(node));
void init() // 초기 설정
{
head->next = tail;
head->prev = nullptr;
tail->next = nullptr;
tail->prev = head;
}
void addFront(int data)
{
node* newNode = (node*)malloc(sizeof(node));
newNode->data = data;
newNode->prev = head;
newNode->next = head->next;
node* next = head->next;
next->prev = newNode;
head->next = newNode;
return;
}
void addBack(int data)
{
node* newNode = (node*)malloc(sizeof(node));
newNode->data = data;
newNode->next = tail;
newNode->prev = tail->prev;
node* prev = tail->prev;
prev->next = newNode;
tail->prev = newNode;
return;
}
void addNode(int num, int data) // num번째 (head->next 기준 0부터 시작) 노드 뒤에 추가
{
node* newNode = (node*)malloc(sizeof(node));
node* prev = head->next;
newNode->data = data;
for (int q = 0; q < num; q++) // num은 0부터 시작한다.
{
prev = prev->next;
}
node* next = prev->next;
newNode->prev = prev;
newNode->next = next;
prev->next = newNode;
next->prev = newNode;
}
void delFront()
{
node* delNode = head->next;
node* next = delNode->next;
head->next = delNode->next;
next->prev = head;
free(delNode);
return;
}
void delBack()
{
node* delNode = tail->prev;
node* prev = delNode->prev;
tail->prev = prev->prev;
prev->next = tail;
free(delNode);
return;
}
void delNode(int num) // num번째 (head->next 기준 0부터 시작) 노드 삭제
{
node* delNode = head->next;
for (int q = 0; q < num; q++)
{
delNode = delNode->next;
}
node* next = delNode->next;
node* prev = delNode->prev;
next->prev = prev;
prev->next = next;
free(delNode);
return;
}
void printList()
{
node* temp = head->next;
while (temp != tail)
{
printf("%d ", temp->data);
temp = temp->next;
if (temp != tail)
{
printf("-> ");
}
}
printf("\n");
return;
}
int main()
{
init();
addFront(5); addFront(3);
addBack(1); addBack(4);
// 3 -> 5 -> 1 -> 4
printList();
delFront(); delBack();
// 5 -> 1
printList();
addNode(1, 8); addNode(1, 6);
// 5 -> 1 -> 6 -> 8
printList();
delNode(2);
// 5 -> 1 -> 8
printList();
return 0;
}
<Node 구조체 선언 및 초기화>
typedef struct Node
{
int data;
Node* next;
Node* prev;
}node;
node* head = (node*)malloc(sizeof(node));
node* tail = (node*)malloc(sizeof(node));
void init() // 초기 설정
{
head->next = tail;
head->prev = nullptr;
tail->next = nullptr;
tail->prev = head;
}Node라는 구조체를 선언해 주었습니다.
Node는 저장할 값(data), 노드 앞(next), 노드 뒤(prev) 주소를 저장해야 합니다.
next와 prev는 주소값을 저장해야 하므로, 포인터로 선언하였습니다.
next와 prev는 Node*라는 타입을 이용했는데요,
이 타입을 이용한 이유는 각 노드들은 이 타입으로 선언되고, 이 주소값을 저장하는 것이기 때문에
결국 그 노드들과 타입이 같아야 하기 때문입니다.(int 타입의 포인터에다 char 타입의 주소를 넣어줄 순 없잖아요 ㅎㅎ)
그리고선 head와 tail을 미리 선언해 줬는데요,
head와 tail은 데이터를 저장하지 않고, 그 사이에 있는 노드들에 데이터를 저장할 생각입니다!
init()라는 함수를 만들어 연결리스트를 초기화해줍니다.
head->next = tail; / tail->prev = head;로 설정해 줬어요!
head->prev와 tail->next는 없으니, nullptr로 초기화해줍니다.
노드 추가하기
<맨 앞 노드 추가>
void addFront(int data)
{
node* newNode = (node*)malloc(sizeof(node));
newNode->data = data;
newNode->prev = head;
newNode->next = head->next;
node* next = head->next;
next->prev = newNode;
head->next = newNode;
return;
}맨 앞에 노드를 추가하는 코드입니다.사실 엄밀히 말하자면, 맨 앞은 아닙니다.아까 말했듯, head와 tail에는 데이터를 저장하지 않도록 할 것이기 때문이죠!
일단 노드를 추가하려면 새 노드를 만든 후, 새 노드의 앞, 뒤 노드를 가리키도록 한 다음,
새 노드의 앞 노드의 next, 뒷 노드의 prev를 새 노드로 바꿔주어야 합니다.
일단 동적 변수를 선언해야 하니 malloc으로 선언하였고, 주소값에 접근해야 하기에 포인터로 선언했습니다.
그렇게 선언한 동적 변수 newNode에 next를 head, prev를 head->next로 설정해 줬습니다.
또, head->next를 next라는 포인터에 저장시킨 후,
next->prev와 head->next를 newNode로 설정해 주었습니다.
*free()를 사용하시면 노드 자체가 날아가니 사용하면 안 됩니다!*
<맨 뒷 노드 추가>
void addBack(int data)
{
node* newNode = (node*)malloc(sizeof(node));
newNode->data = data;
newNode->next = tail;
newNode->prev = tail->prev;
node* prev = tail->prev;
prev->next = newNode;
tail->prev = newNode;
return;
}이 코드는 연결리스트 맨 뒤에 노드를 추가하는 함수인데요,
addFront() 설명과 다 같으나, 차이점은 head뒤에 선언하는 것이 아닌 tail앞에 선언하는 것이겠죠?
<원하는 위치에 노드 추가>
void addNode(int num, int data) // num번째 (head->next 기준 0부터 시작) 노드 뒤에 추가
{
node* newNode = (node*)malloc(sizeof(node));
node* prev = head->next;
newNode->data = data;
for (int q = 0; q < num; q++) // num은 0부터 시작한다.
{
prev = prev->next;
}
node* next = prev->next;
newNode->prev = prev;
newNode->next = next;
prev->next = newNode;
next->prev = newNode;
}head->next를 시작으로 새 노드의 뒷 노드를 정한 후, 새 노드를 추가하는 방식의 함수입니다!
윗 코드랑 별 다를 게 없어요.
노드 삭제하기
<맨 앞 노드 삭제>
void delFront()
{
node* delNode = head->next;
node* next = delNode->next;
head->next = delNode->next;
next->prev = head;
free(delNode);
return;
}지우는 코드는 추가하는 코드의 반대로 해주시면 됩니다!일단 지울 코드를 선택해 주세요! delFront()는 맨 앞 노드가 삭제되어야 하니head->next가 delNode가 되어야겠죠!
delNode를 리스트에서 떼어냈으면 이제 그 저장공간은 필요 없으니 해체시켜 줘야 합니다.free(delNode); 로 메모리를 해체시켜줍니다.
<맨 뒷 노드 삭제>
void delBack()
{
node* delNode = tail->prev;
node* prev = delNode->prev;
tail->prev = prev->prev;
prev->next = tail;
free(delNode);
return;
}맨 뒷 노드가 삭제되는 함수입니다.delfront()와 거의 비슷해요!
<원하는 위치에 노드 삭제>
void delNode(int num) // num번째 (head->next 기준 0부터 시작) 노드 삭제
{
node* delNode = head->next;
for (int q = 0; q < num; q++)
{
delNode = delNode->next;
}
node* next = delNode->next;
node* prev = delNode->prev;
next->prev = prev;
prev->next = next;
free(delNode);
return;
}addNode()와 마찬가지로,head->next부터 시작해서 반복문을 통해 삭제할 노드를 찾습니다.(0부터 시작)그 후 위 함수에서 해준 것처럼 노드를 삭제시켜 주면 됩니다!(delNode 앞 뒤 노드끼리 연결시켜줘야 하는 거 아시죠..?)
리스트 출력 & 테스트(main)
<리스트 출력하기>
void printList()
{
node* temp = head->next;
while (temp != tail)
{
printf("%d ", temp->data);
temp = temp->next;
if (temp != tail)
{
printf("-> ");
}
}
printf("\n");
return;
}리스트를 출력하는 방법은 head->next부터 차례로 앞으로 가면서node->data를 출력하는 방법입니다.(tail이 될 때까지!)이 코드는 굉장히 쉬워요!
<main 함수 코드>
int main()
{
init();
addFront(5); addFront(3);
addBack(1); addBack(4);
// 3 -> 5 -> 1 -> 4
printList();
delFront(); delBack();
// 5 -> 1
printList();
addNode(1, 8); addNode(1, 6);
// 5 -> 1 -> 6 -> 8
printList();
delNode(2);
// 5 -> 1 -> 8
printList();
return 0;
}main함수에는 여러분이 원하시는 대로 프로그래밍하시면 됩니다!그냥 테스트 용이니까요!만약 여러분들이 잘 코드를 짰다면이 코드를 실행시킬 시 결과가 이렇게 나올 것입니다.
이렇게 작성하고 보니 초보자 분들이 이해가 잘 되실지는 모르겠네요...ㅠ혹시라도 질문 있으시면(매일 티스토리 확인합니다!) 꼭 댓글 남겨주세요!
감사합니다 :)
2023.05.28 - [Note/알아두면 좋은 포털 사이트 정보들] - Gmail "확인에 사용할 수 없는 전화번호 입니다" 해결법
2023.02.28 - [Diary/코딩 잡 지식] - 코딩 'C언어'에서 "함수" 사용법 쉽게 알려드립니다! - 함수 겉핥기
2022.07.29 - [Note/알아두면 좋은 Git - GitHub 정보들] - 초보자들 신경 써주지 않는 깃허브.. README.md 꾸며보기!