[C 프로그래밍] 동적 메모리_3.이론_연결리스트1(Linked List)

▶1. 연결리스트
이번 포스팅에서는 동적배열처럼 동적메모리에서 자주 사용되는 연결리스트를 알아보자.

연결리스트란
- 구조체와 포인터를 이용해 유동적으로 데이터를 저장할 수 있는 자료구조
- 배열과 다르게 필요할 때 마다 데이터를 추가할 수 있는 매우 유용한 구조
- 배열과 다르게 필요할 때마다 데이터를 추가할 수 있는 구조

동적 배열의 성질을 생각해보자. 보통 기본자료형을 처음부터 정하고, 인덱스를 통해 접근한다. 
역으로 생각해서 배열이 인덱스로 접근할 수 있는 이유는 자료형을 알고있기에 첫 위치만 알면 N번째 데이터를 읽어올 수 있기 때문이다.

그렇다면 인덱스를 사용할 수 없는 경우는 무엇일까? 간단하게 3가지로 나눌 수 있을 것이다.
1. 자료형의 크기를 모르는 경우
2. 각 데이터가 중간중간 떨어져 있는 경우
3. 자료형의 크기를 모르고 각 데이터가 중간중간 떨어져 있는 경우

이 중 2번은 기본자료형을 사용할 경우 굳이 고려해야되나? 의문이 든다. 일단 1번, 3번에 초점을 맞춰 아래 내용을 학습하자.

▶2.자기 참조 구조체
리스트를 쓰기위해선 먼저 흔히 Node 라고 부르며 쓰는 '자기 참조 구조체'에 대해서 알아야 한다.

struct Node
{
	int n; //가지고 있는 값
	struct Node* next; //자신과 동일한 타입인 Node 구조체를 가리킬 수 있는 포인터
}

– 자신과 동일한 구조체를 가리킬 수 있는 포인터 변수를 필드 변수로 가지는 구조체 
– Node 구조체가 있을 때, 자신과 동일한 타입인 Node 구조체를 가리킬 수 있는 필드 변수가 있어야 한다

일단 구조체를 이용하면 다양한 데이터를 담을 수 있다.

struct Node
{
	int value1; //값1
	int value2; //값2
	double value3; //값3
	float value4; //값4
	char value5; //값5
}

여기에 자신과 같은 구조체 타입을 참조할 수 있는 포인터 변수를 가지고 있는 것이 자기 참조 구조체라 볼 수 있겠다.

struct Node
{
	int value1; //값1
	int value2; //값2
	double value3; //값3
	float value4; //값4
	char value5; //값5
	struct Node* next;
}

굳이 Node를 Node라고 할 필요는 없다. int a의 a 처럼 변수명에 속한다. 좀 더 자세한 설명은 구조체 포스팅에서 다룬다.

▶3. 구조체와 자기 참조 구조체, 배열 리스트(ArrayList)와 연결 리스트(LinkedList)
이제 자기 참조 구조체로 연결 리스트를 어떻게 구현할 것인지 다음 사진을 보자.

– 자신과 동일한 구조체를 가리킬 수 있는 포인터 변수가 있기 때문에, 같은 종류의 구조체 연결할 수 있다.
– 사슬처럼 연결되어 있는 형태가 되고 포인터에 연결되어 있는 모든 데이터에 접근가능하다. 
– 첫 Node의 주소만 가지고 있으면 연결되어 있는 나머지 Node에 모두 접근이 가능

아직 이 형태로는 부족하다. 첫번째 Node에 접근할 포인터를 하나 더 존재해야만 연결리스트를 사용할 수 있는 형태가 된다.

head에 첫 노드를 가리키게 해놓는다면 a,b,c의 데이터 모두 접근할 수 있다.
a의 value :  head->value
b의 value : head->next->value
c의 value : head->next->next->value

의문이 드는 사람도 있을 것이다. 그럼 sizeof로 구조체의 크기를 구하고, 메모리에 바로 다음다음을 연결해놓는다면 배열처럼 인덱스를 쓸 수 있지않을까? 맞다. 그렇게 되면 굳이 자기참조구조체를 쓸 필요도 없다. 이 때 쓰이는 것이 배열 리스트(ArrayList)이다.

그럼 친숙한 배열과 비슷한 배열리스트부터 하는 방법을 알려주지 왜 연결리스트를 할까 의문이 들 수도 있는데, 여기에 대해서는 다음에 자세히 다루고자 한다. 간단한 언급하자면 1.메모리 활용 측면 2.연결리스트의 노드 생성, 삭제 등의 기능 구현 관점 3. Big-O계산에 관점 등이 있다. 여러 면에서 연결리스트가 더욱 장점을 보이기 때문에 배열리스트는 잘 쓰이지 않는다.(간혹 필드에서 옛 기업 프로그램이나 오래된 회사의 소스를 보면 ArrayList가 써이는 경우가 있다고 들은 적이 있다.)


▶4. 연결리스트의 제대로된 활용을 위한 구조. head와 last
연결리스트에 접근하기 위해서 첫 노드를 가리키는 head라는 포인터 변수를 썼다. 그러면 last는 무엇을 가리킬까? 단어만 봐도 알 수 있듯이 맨 마지막 노드를 가리킨다.

last 변수는 무엇에 쓰일까? last 변수는 "언제나 마지막 노드를 가리킨다"라는 조건이 있다. 이를 통해 첫째로 생각할 수 있는 용도는 '노드 추가'이다. 윗 사진에서 새로운 Node인 d를 추가한다고 하자. 그러기 위해선 c노드에 접근해야 하는데 head로 접근하면 3번의 참조를 따라가게된다. 만일 100개의 노드로 된 연결리스트라면? 100번 참조를 따라가야한다. 하지만 last를 사용하면 100만개 노드로 된 연결리스트라도 한 번이면 마지막 노드를 찾을 수 있다. 

새로운 노드를 추가할 때 순서는 다음과 같다.
1.새롭개 추가할 노드 d를 동적메모리 할당을 통해 만든다.
2. 포인터 last 를 통해 next에 접근하고 그곳에 만들어둔 노드 d를 참조하게 한다.
3. last가 노드 d를 가리키도록 변경한다.

이 외에도 마지막 노드 삭제 등 last를 이용하면 연결리스트 활용에서 효율적이게 쓸 수 있다.


▶5. 이후부터의 포스팅에선 실습 위주로 연결리스트의 생성, 삭제, 중간 삽입, 중간 삭제 등을 차례대로 진행하면서 위에 다뤘던 내용들을 자세히 알아보자.