6. 자료구조 - 연결 리스트 : 도입

● data structure

 

자료구조란 프로그래밍 언어에 있는 프로그래밍 구조일 뿐이다. 자료구조는 컴퓨터 메모리에 정보를 각기 다른 방법으로 저장할 수 있도록 해준다.

 

위 3가지 기능을 통해 새로운 기능을 만들 수 있다.

 

1. struct

 

struct 는 구조체이다. C 에서 자신만의 구조를 만들 수 있는 키워드이다. 선형검색 파트에서 person 구조체를 만들어서 그 안에 name과 number 를 넣었다. 이렇게 두 개의 값을 가진 사용자만의 자료 종류를 만들 수 있었다.

 

2. .

.(점) 연산자는 구조체의 속성값을 가져올 때 사용했다. 따라서, person 구조체의 name 이나 number를 가져오려면 변수 이름과 . 연산자를 통해서 자료 구조 안으로 들어가야 했다.

 

3. *

 

* 연산자는 이 부분에서는 서로 다른 맥락에서 약간 다른 의미를 가질 수 있지만, 항상 메모리와 연관되어 있다. 포인터를 이용하여 메모리 덩어리로 접근할 수 있는 역참조 연산자이다.

 

앞으로 배울 것은 이 기본적인 원칙들로 요약될 수 있다는 것을 명심하자.

 

 

● linked lists

 

연결 리스트는 값들의 리스트를 저장하는 방법이다.

 

물론, 배열도 값들의 리스트를 저장할 수 있었다. 하지만, 배열은 고정된 메모리 덩어리라는 단점이 있다. 그래서 배열의 크기를 조절해서 더 많은 값을 넣고 싶다면 우선 최소한 더 많은 메모리를 할당해야 했다. 또한, 기존 배열에서 새 배열로 이 모든 값들을 복사해야 했다. 물론 realloc 이 이를 좀 더 간단하게 해주는 함수였다. 하지만, realloc 도 결국 완전히 같은 작업을 하는 것이다. 그렇기 때문에 배열에 값을 추가하는 과정은 O(n) 이 되었다.

 

배열의 장점은 [] 를 이용하여 문법적으로도 쉽게 인덱싱할 수 있고 랜덤 접근이라는 방법으로 일정한 시간에 접근할 수 있다. [] 에 0, 1, 2를 사용하여 바로 그 자리로 접근할 수 있었다. 이런면에서 배열은 매우 빠르다. 또한, 이진 탐색같은 곳에서도 적용할 수 있었다.

 

하지만, 컨버스 같은 컴퓨터 메모리를 조금 더 현명하게 사용할 순 없을까??

1을 저장하고 싶다고 해보자. 임의로 0x123 에 저장했다고 하자. 이것은 크기가 1인 배열이라고 생각하고 이 배열에 2번째 값을 넣고 싶다고 생각해보자. 즉, 리스트를 만들고 싶은 것이다. 현재 리스트의 크기는 1이다. 

또한, 이 메모리에는 1 주변에 많은 값들이 존재할 것이다.

 

그래도 빈공간을 찾아서

그 빈공간에 2를 저장할 수 있다고 해보자. 주소는 0x456 이다.

 

마지막으로 3번째 값을 저장해보자.

3을 빈 공간에 저장하고, 주소는 0x789 이다.

 

현재 이것은 정의상 배열이 아니다. 1, 2, 3이 서로 인접해 있지 않기 때문이다. 여기서는 [] 를 사용할 수 없다.

 

그런데 만약 아래와 같이 1, 2, 3과 같은 값을 저장하기 위한 하나의 메모리 덩어리만 사용하지 않고 2배의 메모리를

줘서 조금 더 유연하게 만들어보자.

그래서 2개의 메모리 덩어리가 각각 1, 2, 3을 나타내게 된다.

그리고 각 덩어리의 나머지 반은 어떻게 사용할까??

 

나머지 반에는 아래와 같이 다음 메모리 덩어리의 주소를 가지는 것이다.

즉, 만약 위 리스트들을 정렬된 상태로 유지하는 것이 목표여서 1, 2, 3을 담은 리스트를 만들고 싶다면 각 메모리 덩어리의 반에 pointer를 저장하는 것이다. (다음 메모리 덩어리를 가리키도록 한 것) 

 

1번째 덩어리의 반에는 2를 담은 메모리의 주소를 넣고,

2번째 덩어리의 반에는 그 다음 메모리 덩어리를 가리키게 하는 것이다.

마지막 메모리 덩어리의 반은 특별한 값이 필요하다. 이 리스트에 더 이상 남은 것이 없다는 것을 나타내기 위한 적절한 임의의 값으로 NULL 을 사용한다. \0 와는 다르다. NULL 은 0x0 을 말한다. 포인터인 것이다. 물론 \0 이나 NULL 모두 값은 0을 나타낸다.

 

마지막 NULL 을 통해 리스트의 끝을 알리는 값을 저장했다.

이제 어떤 값이 실제로 메모리의 어디에 있는지는 중요하지 않다. ( 메모리 주소 자체는 신경쓰지 않는다는 의미 )

 

그래서 아래와 같이 포인터를 화살표로 나타낸다.

 이제 이 1, 2, 3 숫자 리스트는 연결되어 있다.

 

linked lists 는 메모리 덩어리 여러 개를 포함한 데이터 구조이다. 그리고 이 메모리들이 포인터로 연결되어 있다. 하지만, 그 대가로 원래의 배열에서는 1, 2, 3 만 저장했지만 연결리스트에서는 숫자 1, 2, 3 과 3개의 포인터를 더 저장하기에 2배의 메모리가 필요하다. 

 

이렇게 포인터를 이용하여 메모리에 새로운 구조를 만들 수 있게 되었다. 

 

이 구조를 개별적으로 보면 모두 2 개의 필드를 가지고 있다.

첫 필드는 정수이고 이곳을 number 라고 부르자.

두번째 필드는 관례적으로 next 라고 부르고, 리스트의 다음 요소를 가리키는 메모리 덩어리이다.

 

이 새로운 구조체를 코드를 통해 만들어보자.

우선 typedef 를 통해서 struct node 의 이름을 node 라고 정의한 것이다. 

그리고 이 node 안에는 int 와 또 다른 struct node 를 가리키는 포인터 변수 next 가 존재한다.

 

즉, 위 이미지에서 본 직사각형 메모리 구조를 node 라고 정의한 것이다.

여기서 node 는 직사각형으로 나타낼 수 있는 메모리 덩어리를 의미한다.

그리고 node 의 값으로는 2가지를 저장해야 하는데, 하나는 number 라고 불리는 int 이고,

또 다른 하나는 관례적으로 next 라는 이름을 가지고 struct node 를 가리키는 포인터가 온 것이다.

 

typedef 를 통해 만든 새로운 자료구조인 모든 node 노란색 직사각형 상자에는 number와 next 포인터가 존재하게 된다. next 포인터는 node 구조체를 가리키도록 정의한 것이다. 그리고 이 struct node 를 node 라고 선언한 것이다.

 

 

자료출처 : 부스트코스 - https://www.boostcourse.org/cs112/lecture/119038?isDesc=false