6: 자료구조-3(연결 리스트: 도입)

자료 구조: C, C++, 자바, 파이썬에 있는 프로그래밍 구조

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

데이터 구조는 우리가 컴퓨터 메모리를 더 효율적으로 관리하기 위해 서로 정의하는 구조체 

일종의 메모리 레이아웃, 또는 지도라고 생각할 수 있음

 

1) 구조체(struct)

-  C에서 자신만의 구조를 만들 수 있는 키워드(예, person 구조체에 이름과 번호)

2) .

구조체의 속성 값에 접근할 때 사용(속성 값을 가져올 때 사용)

3) *

메모리 덩어리로 접근할 수 있는 역참조 연산자

---

배열 

장점: 쉽게 인덱싱할 수 있음 단점: 고정된 값

배열에서는 각 인덱스의 값이 메모리상에서 연이어 저장되어 있음

 

연결 리스트 : 각 값이 메모리 상의 여러 군데에 나뉘어 있어도  다음 값의 메모리 주소를 기억해서 여전히 값을 연이어 읽어 들이는 것

메모리 덩어리 여러 개를 포함한 데이터 구조(어떤 방식으로든 연결되어 있음)

 

크기가 3인 연결리스트

- 그림과 같은 연결 리스트는 각 인덱스의 메모리 주소에서 자신의 값과 함께 바로 다음 값의 주소(포인터)를 저장함

- 연결 리스트에서는 숫자 1, 2, 3 뿐만 아니라 3개의 포인터를 더 저장해서 2배의 메모리가 필요함

- 연결 리스트의 가장 첫 번째 값인 1은 2의 메모리 주소를, 2는 3의 메모리 주소를 함께 저장하고 있음

- 3은 다음 값이 없기 때문에 NULL을 다음 값의 주소로 저장함

- NULL은 문자 \0을 뜻하는 것과는 다름 NULL은 포인터(리스트의 끝을 알리는 값)

---

연결 리스트의 구조체 정의

 

typedef struct node
{
    int number;
    struct node *next;
}
node;

 

- node는 직사각형으로 나타낼 수 있는 메모리 덩어리를 의미함

- node라는 이름의 구조체는 number와 *next 두 개의 필드가 함께 정의되어 있음

- number는 각 node가 가지는 값, *next는 다음 node를 가리키는 포인터

- 여기서 typedef struct 대신에 typedef struct node라고 ‘node’를 함께 명시해 주는 것은, 구조체 안에서 node를 사용하기 위함

 

 

https://www.boostcourse.org/cs112/joinLectures/41307

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