CS50 2019 (16)자료구조란, 연결리스트, 구조체, 연결리스트 코딩, 시연

---

www.boostcourse.org/cs112

모두를 위한 컴퓨터 과학 (CS50 2019)

1.컴퓨팅사고

2.C언어

3.배열

4.알고리즘

5.메모리

6.자료구조

 

---

3)연결 리스트: 도입

∴ 결론 : 연결 리스트는 원하는 만큼 리스트를 크게 만들 수 있다 동적으로. 배열은 리사이징 하고 값을 옮겨야 돼

 

우리는 여러 자료형의 데이터를 메모리 상에 저장하고 읽고 삭제하는 방법을 배웠습니다. 컴퓨터 프로그램은 이러한 데이터를 이용해서 다양한 작업을 수행할 수 있습니다. 하지만 좀 더 복잡한 프로그램을 구현하다 보면 기본적인 포인터 구조만 이용해서 메모리를 관리하기에는 다소 번거로울 때가 많습니다. 만약 메모리를 좀 더 효율적으로 관리하고 사용할 수 있다면 어떨까요? 이번 강의에서는 데이터 구조의 개념과 연결 리스트에 대해 알아보겠습니다.

 

---

지난 시간까지 하던 것중, 더 높은 수준의 방법 생각해보기

좀 더 멋진 자료 구조를 이용하는 다른 방법

 

---

자료구조란,

C, C++, JAVA, Python에 있는 프로그래밍 구조일 뿐

서로 다른 언어에서 자료 구조를 보게 될 것이다

자료구조는 여러분의 컴퓨터 메모리에 정보를 각기 다른 방법으로 저장할 수 있도록 해준다

 

---

오늘 우리가 C에서 하려는 것은 세가지 기능으로 만들 수 있다

구조체 : C에서 자신만의 구조를 만들 수 있는 키워드

ex)person구조체에 이름과 번호가 들어가 있었다. 두개의 값을 가진 우리만의 자료 종류

 

비트맵이나 비트맵 헤더 등과 관련된 문제에서도 구조체를 사용한다. 이런 것들 또한 자료구조다.

 

. 표기법 : 구조체의 속성값을 가져올 때 사용한다

person 구조체의 이름이나 번호를 가져오려면?

변수이름과 점 연산자를 사용해서

person. 으로 자료구조 안으로 들어가야 한다

 

* 별표 연산자 : 다른 맥락에서 다른 의미를 가질 수 있다. 하지만 항상 메모리와 관련돼 있다.

포인터를 이용해서 메모리 덩어리로 접근할 수 있는 역참조 연산자.

 

---

이 기본적인 원칙 3개로 요약하고 더 흥미로운 해결책을 만들어볼 거야!

 

---

연결리스트 등장!

값들의 리스트를 저장하는 방법.

배열도 가능했잖아?

배열은 단점이 있었어. 고정된 메모리 덩어리야.

배열의 크기를 조절해서 더 많은 값을 넣고 싶다면 일단 최소한 더 많은 메모리를 할당해야해 또 기존 배열에서 새 배열로 모든 값들을 복사해야해

 

realloc은 이를 더 간단하게 만드는 기능이지만, 결국 완전히 같은 작업을 하게 된다. 사물함 간에 값을 복사하고 메모리를 free하고..

 

그래서 이렇게 배열에 값을 추가하는 과정은 O(n)이 된다

배열 전체를 새 공간에 복사하는 데 시간이 오래 걸리기 때문

 

배열을 버리고 싶지는 않으니까, 배열의 장점은?

대괄호를 이용해서 문법적으로 쉽게 인덱싱 할 수 있고

랜덤 접근이라는 방법으로 일정한 시간에 접근할 수 있다. 무엇이 어디에 있는지 알 수 있다는 면에서 랜덤은 아니다.(??) 괄호에 0, 1, 2등을 써서 바로 그 자리로 접근할 수 있다

 

사람은 사물함에 걸어가야하기 때문에 시간이 걸리지만

컴퓨터는 0, 1, 2, 3번의 위치로 바로 접근할 수 있다  ▽이게 랜덤 접근인가보군

 

그래서 배열은 아주 빠르다

 

또 배열은 바이너리 검색 같은 곳에 적용할 수 있다

 

---

배열에서 벗어나

캔버스 같은 컴퓨터 메모리를 조금 더 똑똑하게 사용해보자!

모든 요소들을 서로서로 옆에 붙이면서 계속 추가할 수 있을 만큼 메모리가 남아있기를 바라기보단, 이 문제를 조금 더 똑똑하게 해결해보자

 

지난 시간에 컴퓨터에 있는 모든 바이트는 어디엔가 저장이 돼 있다고 배웠다 - 뭔말?

그렇기 때문에( - 뭔말?) 1이 0x123에 저장돼 있다고 해봅시다

크기가 1인 배열이라고 생각하고, 이 배열에 두번째 값을 넣고 싶다고 생각해보자.

아니면 조금 더 일반적으로 list라고 부르자. 실제 현실의 list처럼 값으로 이뤄진 list

이 list의 크기는 1

이 메모리에는 아주 많은 다른 값들이 방해하고 있을 것

 

하지만 컴퓨터 메모리의 저 아래쪽에 약간의 공간이 비어있다고 해보자. 바로 옆이나 근처는 다른 값들이 존재해서 사용할 수 없어.

근데 저 부분쯤에 사용할 수 있는 메모리가 있고 여기에 그냥 2를 저장할 수 있는 것. 이 주소가 456이라고 해보자

3은 저~기 789에

이게 정의상 배열은 아니다. 1, 2, 3이 인접해있지 않아

여기선 대괄호를 사용할 수 없어(서로 붙어있어야 한다)

모든 곳에 퍼져 있어. 컴퓨터 메모리에서 이 공간들만 사용할 수 있었기 때문.(인접한 애들은 못썼어서)

 

좀 사치를 부려서 1, 2, 3과 같은 값을 저장하기 위해 하나의 메모리 덩어리만 사용하지 말고, 두배의 메모리를 줘서 조금 더 유연하게 만들어보자

그래서 이제 두개의 덩어리가 1을 나타내게 됨.

이 묶음은 2

이 묶음은 3

 

그럼 저 나머지 반은 어디에 사용하면 좋을까?

예를 들어 이 리스트들을 정렬된 상태로 유지하는 것이 목표라서 1, 2, 3을 담은 리스트를 만들고 싶다면?

=>다음 메모리 덩어리의 주소다

또, 리스트의 마지막엔 이 리스트에 더 이상 남은 것이 없다는 것을 나타내기 위한 특별한 값이 필요.

적절한 임의의 값. NULL

문자 \0와는 엄밀히 다른 것이다

이것은 16진법 0이다 0x0

지난주에 간단하게 살펴봤던 NULL이라는 것은 문자 \0을 뜻하는 NULL과는 다른 것이다

NULL은 포인터, 하지만 둘 다 그 값을 보면 0

 

---

실제로 메모리의 어디에 있는지는 중요하지 않다고 했어. 그러니까 그거 빼고 포인터를 화살표로 나타내면

1, 2, 3 숫자 리스트는 연결이 돼 있어 보인다

 

연결 리스트는 메모리 덩어리 여러 개를 포함한 데이터 구조이다. 어떤 방식으로든 연결돼있다.

이 메모리들이 포인터로 연결돼 있고,

그 대가로 원래의 배열에서는 숫자 1, 2, 3만 저장하다가, 3개의 포인터를 더 저장해. 2배의 메모리가 필요하다(두개 포인터가 사용되고, 나머지 하나는 리스트에 뭔가 추가된다면 그곳을 가리키게 됨)

 

메모리에 저렇게 생긴 구조를 만들었다! 포인터 기능을 이용해서!

 

---

이 구조를 개별적으로 보면

두개의 필드를 갖고 있다

하나는 정수

나머지 하나는 맘대로 불러도 되는데 관례적으로 next라고 부른다. 리스트의 다음 요소를 가리키는 메모리 덩어리

 

---

이걸 했었지. 똑같은 문법으로 

 

node라고 부르고  --컴퓨터 공학에서 node라는 단어는 직사각형으로 나타낼 수 있는 메모리 덩어리를 의미한다. 수학이 익숙하다면 그래프에 있는 노드와 비슷한 역할.

어떤 값을 저장하냐면 두가지.

int랑

int 포인터인줄 알았는데 아니고 node라는 구조로 돼 있어.

엄밀하게는 이렇게 할 순 없어.

C는 문자 그대로 받아들여서, 위에서 아래로, 왼쪽에서 오른쪽으로 읽어

어느시점부터 node라는 단어가 존재하게 되는 걸까?

마지막 줄 이전에는 존재하지 않는 단어야. 여기서 정의해

 

그래서 안타깝게도 node안에서 node를 쓸 수는 없어. 맨 뒷줄을 보기 전까지 node라는 단어는 컴퓨터에 존재 하지 않기 때문

 

해결방법은??

typedef struct라고 쓰는 대신, typedef struct node라고 써서 사용하고자 하는 단어를 추가해준다

그러면 안에서

struct node *를 쓸 수 있게 된다

 

모든 node는 숫자와 포인터가 있다!

그리고 포인터는 node구조체를 가리키도록 정의돼 있다.

 

▽어떤 자료형을 가리키냐도 정확히 해야되네 할당하는 크기가 다른가봐 다 같은 주소인줄 알아서 메모리 어디 가르켜라~가 아니었어

 

아래에 또 node써줘야 되는건 별명이래. 맨 위에 쓴게 정식 명칭이래

별명은 프로그램의 다른 부분에서 사용하기 쉽도록 쓴 것

 

node대신 x를 썼으면 : typedef struct x  --구조체의 정식 명칭이다.

밑에 struct x *next;이렇게 써주면 되고

 

---

4)연결 리스트: 코딩

지난 강의에서 연결 리스트의 정의와 리스트의 기본 단위가 되는 구조체를 정의하는 방법을 배웠습니다. 이번 강의에서는 이 구조체를 이용하여 실제로 연결 리스트를 구현하고 사용해보도록 하겠습니다.

 

---

만들었던 구조체로 뭘 할 수 있을까? 뭔가 만들어보자

연결리스트를 구현하는 코드!

 

첫 연결리스트는 어떻게 나타내야 할까?

리스트의 처음건 비어있어. 비어 있는 무언가를 나타날 때는 최소한의 무언가가 필요해

빈박스로 나타내고 이것을 node를 가리키는 포인터라고 해보자.

아직은 비어 있는 연결리스트를 구현해보면

이렇게 node *list에 NULL로 지정

NULL로 초기화 해줬기 때문에 어떤 메모리 덩어리를 가리키는 화살표가 아직은 없다는 것

▽node가 구조체니까 안에 값 2개가 들어가는데 일단 없다고 NULL하는 듯(X) 이게 아니고 포인터잖아 아무것도 안가리키고 있다고

1, 2, 3 모두 없고, 들어 있는 숫자가 없다면 적어도 리스트가 없다는 것을 알려주는 변수가 있어야 한다.

값이 없을 때 이를 표현하는 가장 간단한 방법은 0을 저장해서 NULL이라는 새로운 별명을 가지도록 하는 것

 

---

이젠?

이거 하면 된다. 몇 바이트 만큼 malloc해? node의 크기를 알 수 없어. 계산을 통해 정수와 포인터를 더할 수도 있지만 sizeof쓰면 바로 알 수 있다

 

이렇게 이 코드가 node를 저장할 만큼의 메모리 덩어리를 할당해주고

변수 n에 저장

 

---

더 나아가서 그럼 값을 저장할 수 있다

이 문법은 뭐야?

*n은 가리키는 곳으로 간다

괄호는 연산의 순서를 위해서 넣었다 -> 컴파일러는 이를 인식해서 먼저 처리하게 된다

그럼 거기 가서 number필드에 접근한다. 배웠던 점 표기법을 사용.

 

따로 배웠던 두가지를 한번에 하는 코드야

n(포인터)에 있는 주소에 해당하는 메모리 덩어리로 가서, number필드에 접근해서 2로 만들어주는 것

다행히도, C에는 이를 더 간단하고 예쁘게 표현할 수 있는 문법이 있다

이 화살표 기호다

이게 우리가 배우게 될 마지막 문법

- 와 > 를 사용하는 매우 독특한 문법
위의 저 코드와 정확히 같은 코드다.

▽구조체에 쓰나봐, 구조체를 가리키는 포인터 + 구조체 필드

 

---

이제 node의 주소를 넣으면 되는데, 아직 다음 node가 없어. 그럼 대신 NULL을 넣으면 된다고 했다.

화살표 기호로 * . () 안쓰고 해결!

 

---

그리고 malloc을 사용할 때마다 검사를 해줘야 한다

반환된 값을 항상 체크해야 해

정밀하게 코드를 짜기 위해, 코드에 몇 줄을 추가해서 n이 null이 아닌지 검사

n이 null이면 프로그램을 끝내거나 리턴 해도 됨.

어쨌든 중요한건, n이 널인지 아닌지 확인되기전까지는 n을 건드리거나 화살표 기호를 사용해서는 안돼

 

---

지금 이 상태

아직 연결이 이뤄지지 않았다.

어떤 포인터에서 구조체로 향하도록 하는 것과 같은 행동을 해야한다. 화살표를 구현해야해

궁극적으로는 이렇게!

어떻게 해?

이렇게 하면 끝이다  ▽list랑 n이랑 따로 있었어 둘다 node *였고, 아마 아래서 할 추가를 위해 나눠놓은듯?

list라는 변수가 있고, 원래 NULL로 초기화 돼 있었지만

n은 새로운 node를 갖고 있는 임시 변수야

->덮었으니 이제 list는 더 이상 null이 아니다

 

그림 구현 끝!

 

---

list에 숫자 4를 추가

4는 자체 노드 안에 들어있어

코드로 구현하려면 4를 넣기 위한 새로운 node를 할당받자

그리고 연결해야지 값을 2를 가지는 노드의 포인터가 4를 가리키도록

이걸 하기 위해 임시로 포인터 tmp를 하나 선언해서 해볼게

▽왜 임시를 선언하지? node *n = malloc() 한 다음 n->number = 4; 하고, n가지고 list랑 같은거 가리키는거 부터 시작해서 값 큰지 작은지 따지다가 들어갈 자리 생기면 어차피 n의 값이 더 작을 때 그 전에 애랑 똑같은걸 가리키고 있으니까 그 전에것이 n을 가리키면 끝 아니야? 그냥 임시 한번 썼나봐

저 밑에 연결리스트 시연 보니까 별 의미 없다.

tmp로 가다가 들어갈 자리 판단 됐을 때 그냥 노드포인터가 가리키게 해(n->next = tmp)

 

---

tmp는 처음에 list랑 같은걸 가리키고

그 구조체의 next가 null인지 체크해.

null이면? 리스트의 끝을 찾은 것

이게 거기에 4가 적혀 있는 node를 가리키도록 화살표를 그려주면 돼

 

null이 아니면? while문을 쓴다

while()안이 새로워 보일 수 있는데 그냥 질문을 던지는 거야

가리키는 곳이 널이 아니면 다음의 코드를 실행하는 것  =▽널이 아닌 그 값을 다시 tmp에 넣는다

그 자신이 가리키고 있는것을 가리키도록 한다!

 

얼마나 리스트가 크든 계속해서 임시 포인터를 움직여서 NULL을 찾을 때까지 따라간다

 

---

다시 말하지만 얘네는 컴퓨터 메모리에 흩어져 있다. 사용 가능한 공간이 어디 있는지는 크게 상관이 없다.

 

---

만약 리스트의 순서를 유지하면서 1을 추가한다면? 중간에 들어가야 돼

1)일단 새로운 node할당

2)화살표를 이렇게 바꿔야

근데 이러면 더이상 아무도 2를 가리키지 않으니까 2가 버려지면서 4와 5도 버려진다. 값들을 모두 잃어버려 = 메모리 누수

 

Valgrind를 사용할 때, 메모리가 누수돼서 경고를 일으킨다면 메모리를 free하는 것을 잊었기 때문일 것

아니면 더 심한 경우는 여러분이 사용하던 메모리를 완전히 잃어버린 것일 수도 있습니다.

 

저 코드에 따르면 이 메모리에 다시는 접근할 수 없다

이 값들이 어디에 있는지 기억하고 있는 변수가 없기 때문

 

---

그래서 먼저 list가 가리키고 있는걸 저장을 해놔야 해 1이 2를 먼저 가리키는걸 먼저하면 된다

그 다음 list가 1을 가리키도록 하기

이 모든 과정은 코드 두줄로 구현할 수 있다

1을 가리키고 있는 방금 할당한 새로운 node의 next필드를 업데이트 할 때 list가 가리키고 있는 곳을 넣는 것

list는 n그 자체를 가리키도록 하면 된다

 

---

3을 넣어볼까? 순서를 맞추려면 리스트의 중간에 넣어야 해

1)역시 일단 메모리 할당 먼저 받아야겠지

2)위에서 봤던것 처럼, 먼저 2가 바로 3을 가리키게 하면 안되고, 2가 가리키는 것을 3도 같이 가리키게 먼저 해야 한다

3)그 다음 2가 3을 가리키게

정확한 코드

1)포인터를 만들고

2)루프를 이용해서 원래 존재하던 리스트를 탐색하면서 부등호를 사용해서 삽입할 적절한 위치를 찾아낸다

3)포인터 업데이트

 

---

맨 뒤에 추가하는게 젤 쉽고

그 다음은 맨 앞에 추가하는 것이 쉽다

 

---

질문타임)

질문 하는 친구도 node *n = malloc(~~ 를 헷갈려 하네

 

n은 포인터고 node가 아니야. *n이 노드야

node를 가리켜

node는 malloc으로 할당해서 만들고

 

---

5)연결 리스트: 시연

연결 리스트와 배열을 비교해보고 그 장단점을 생각해 보겠습니다

 

---

친구들과 전시간에 했던걸 반복함

사람 한명 한명이 메모리의 힙을 나타내게 됨

처음 한명은 연결 리스트 그 자체를 나타내야한다. 가장 먼저 NULL로 초기화를 진행 = 뒷짐지고 아무것도 가리키지 않기

재밌네.. 청춘이네..

이 다음 우리는 2, 4, 5, 1, 3을 넣을건데

 

2를 넣기 위해 어떤 기본적인 연산을 할까? = 코드 첫번째 줄이 뭐가 될까?  ▽malloc()이겠지

2가 들어갈 node를 malloc해야 한다. 두가지 필드가 있어서 2랑 화살표를 받음

그리고 얘의 포인터는 아무데도 안 가리킬 거니까 뒷짐

그럼 이제 list가 2를 가리킨다

list가 2를 가리키고, 2는 널포인터가 있다

 

---

리스트에 4추가하기

malloc, 4넣고, NULL넣고

 

이때 임시 변수가 필요(▽왜 필요하지 그냥 하는건가)

임시변수는 list가 가리키는 것과 똑같은 것을 가리킨 다음, 진행하면서 값 크기 비교를 한다

내것이 더 크면 keep going. 그때 아무것도 안가리키고 있다면? 자기가 젤 큰것이고, 그걸 4를 가리키게 하면 된다

 

5는 과정이 똑같아

 

---

1은?

malloc, 1과 null갖게 하고

임시변수를 만들어서 list와 같은걸 가리킨 다음

(더 작다고 먼저 list가 임시변수를 가리키면 뒤를 잃는다. 더 이상 복구하거나 free할 수 없게 메모리가 누수된다)

진행해서 다음걸 계속 가리키다가 값보다 내가 작으면 그대로 두고, 그 전에 애가 나를 가리키게 한다

3도 마찬가지

 

끝

 

---

연결리스트의 단점

 

연결리스트는 메모리 덩어리들로 이뤄져 있다. 배열이나 똑같이 생긴 사물함들 처럼.

우리 눈은 12345라는 숫자를 한번에 볼 수 있었지만(▽엄밀히는 아니겠지)

컴퓨터는 한 번에 하나의 메모리만 볼 수 있다

 

이 말은

컴퓨터에게는 연결 리스트가 이렇게 보인다는 말

연결 리스트에 있는 숫자들은 아무것도 보이지 않아. 모든 메모리를 하나씩 열어봐야 해

 

그래서 3이 어디로 가야 하는지 알려면 처음부터 열어봐야 하고, 최대한으로는 모든 걸 확인해봐야해

 

---

연결리스트로 리스트에 동적으로 추가할 수 있는 기능을 확보해서, (추가적인 숫자들을 malloc하면 된다) 원하는 만큼 리스트를 크게 만들 수 있다.

배열처럼 숫자를 추가하기 위해 크기를 조절하고 기존의 값을 모두 옮기지 않아도 된다는 것

 

그래서 자료구조를 연결리스트로 만들면 역동성을 추구한 것

 = 원래 있었던 것을 움직이지 않고도 리스트를 늘릴 수 있는 능력

 

---

근데 여기서 우리가 잃어버린건 뭐였을까?

임의 접근법을 잃어버렸다 = 리스트의 처음부터 끝까지 가기 위해서는 포인터를 따라가야하고, 중간의 값으로 바로 갈 수는 없다

(https://movahws.tistory.com/88 : 배열의 각 항목들은 메모리상에 자신들의 주소를 갖고 있기 때문에 인덱스 번호만 안다면 어느 데이터에서나 접근이 가능한 random access가 가능하다.)

 

random access를 하게되면 이진 탐색을 잘 사용할 수 있었어

그러므로 이진 탐색을 효과적으로 할 수 있는 능력을 잃었다.

탐색이 O(log n)에서 다시 O(n)이 됐다

한편 삽입의 경우에는 최악의 경우에도 O(n)이 된다. 모든 리스트를 다 둘러보고, 주어진 숫자에 맞는 자리를 찾기만 하면 되기 때문. 순서를 맞추고 싶은 경우에

 

따라서 훨씬 더 동적인 삽입 기능을 얻어서, 더 흥미로운 무언가를 메모리에 만들 수도 있고, realloc에서 했던 것 처럼 값들을 이동하지 않아도 되니 실행 시간이 줄어들 것이라고 생각 할 수도 있지만, 사실 여기에는 대가가 있는 것

 

---

리스트 프로그램의 마지막 예시, 배운 모든 것들이 들어 있다. 아까 학생들이 했던 내용임

list3.c

printf - stdio.h

malloc, free - stdlib.h

처음에 아무것도 없는 상태로 초기화

1, 2, 3 node 추가

return 1을 하면 프로그램이 멈춘대

// Add number to list가

이 그림이야. 저 코드를 실행하면 메모리에 이 그림과 같은게 생겨

 

---

2를 넣는 코드

30번째줄의 n은 똑같이 또 쓴다 어차피 malloc으로 새로운 주소 들어가니까

 

---

3도 똑같아

list->next->next = n; 시범이라서 이렇게 함. 보통 이것을 하드코딩하지 않아. 루프 같은걸 사용해

▽ '->' 는 왼쪽의 포인터가 가르키는 구조체의 오른쪽 이름의 필드 값을 말한다

 

---

이제 이 프로그램의 유일한 목적인 출력

이런식

i++ 같은게 없어서 파격적이어 보여

첫번째는 초기화, 두번째는 조건, 세번째는 업데이트하는 방법

 

▽이런 출력할 때 tmp잡는건 백번 이해가 갑니다만 아까 시연 중에 insert할 때는 왜 잡은건지..

 

---

이 메모리들은 free해야해

어떻게 메모리를 free할지는 좀 더 영리하게 생각해야 하는데, 여기서는 while