제5 장 연결 리스트)
개관)
리스트는 배열과 달리 원소들 간의 논리적인 순서를 표현하기 위한 자료구조다.
개인적으로 이 표현이 정말 리스트라는 자료구조의 핵심 중의 핵심이라 생각한다.
원소들 간의 순서가 논리적으로 지켜진다면 각 원소가 저장되는 물리적인 위치는 어디든 상관이 없다.
배열을 이용하여 리스트를 구현하면(== ArrayList) 원소의 논리적인 순서를 지키기 위해 원소의 이동이 많아진다.
따라서 그것보다 포인터 변수를 이용한 연결 리스트(링크드 리스트, LinkedList)를 이용한다.
포인터 변수를 사용하고 메모리 할당을 동적으로 하면 리스트 구현 프로그램의 실행에 필요한 메모리의 낭비를 막을 수 있고 프로그램 수행도 효율적으로 할 수 있다.
학습 목표에서 중요한 것
리스트와 배열의 차이점이 뭔가요?
용어 정리
리스트: 리스트 자체는 '원소들 간의 순서'가 지켜지며 유지되는 자료구조다.
1. 리스트의 개념
리스트는! 요소가! '일정한 순서'로 유지되는 자료구조다!!!
...
2. 배열을 이용한 리스트의 구현
리스트 원소의 삽입은 프로그램의 실행 중에 메모리 할당을 필요로 하는 경우도 발생시킨다.
따라서 배열을 이용한 리스트의 구현은 실제 IT 서비스 환경에서는 자주 사용되지 않고 있다.
(실무에서 ArrayList 잘 안 쓰나?)
...
3. 포인터를 이용한 리스트의 구현
포인터나 링크나 같은 말이다.
메모리의 저장 위치 주소(메모리 주소)의 구체적인 값은 시스템에 의해 실행될 때마다 결정되므로 개발자는 주소를 몰라도 된다.
추상화된 리스트의 모습과 링크 부분에 해당하는 연결고리만 상상하며 프로그램을 작성해도 된다.
연결 리스트는 '노드' 간의 '포인터' 연결을 통해서 구현되며, 각 노드는 적어도 두 종류의 필드, 즉 원소값을 저장하는 '데이터 필드'와 노드 연결을 위한 '링크 필드'를 가진다.
노드는 C 프로그래밍 언어에서 struct 자료형으로 구현된다.
링크 필드는 C 프로그래밍 언어에서 포인터 변수로 구현된다.
...
책 이미지를 캡쳐 하고 싶은데 저작권을 보호하고 싶어서 참고 있다.
헤드 -> 노드 -> 노드 -> 노드 이렇게 있다고 할 때
헤드는 포인터 변수다.
헤드 다음이 연결 리스트의 시작 노드다. 여기서부터 리스트의 첫 번째 원소가 시작된다. 헤드는 노드가 아니다. 리스트의 처음도 아니다.
마지막 노드는 링크가 널 포인터(Null pointer)로 표현된다.
간혹 마지막 노드의 링크가 널 포인터 변수를 가리킨다고 하는 경우도 있던데
이게 진짜 그림 그리는 주체(?)에 따라 다른 것도 같고 사용하는 언어에 따라 다른 것도 같고
지금 내 수준에서는 이걸 100% 완벽하게 정리하기가 어려우니 그냥 이런 저런 경우가 있다 정도로만 알아 두어도 되겠다.
...
4. 포인터 변수
포인터는 메모리의 주소값을 저장하는 변수다.
int *b;
b = &a; <- & 연산자는 '역참조 연산자'라고 한다. 나는 저걸 & == Address 이렇게 외웠었다.
이 부분 즈음부터 C 문법 얘기가 계속 나오는데 지금은 자료구조 정리 중이라 이에 대해 깊게 정리하지 않는다.
...
5. 구조체 포인터 타입
프로그램의 실행 중에 메모리 공간을 할당받는 함수 = malloc() == Memory Allocation.
교재 101페이지에 나오는 코드에 대한 풀 설명은 아래와 같다.
- 포인터 변수 선언과 초기화: 코드에서 int *p_a;와 float *p_b;는 포인터 변수를 선언합니다. 이 포인터들은 아직 초기화되지 않았으며, 어떠한 메모리 주소도 가리키고 있지 않습니다.
- 동적 메모리 할당과 타입 캐스팅:
- p_a = (int *)malloc(sizeof(int));
- p_b = (float *)malloc(sizeof(float));
- 포인터를 통한 값의 할당:
- *p_a = 10;
- *p_b = 3.14;
- 출력 및 메모리 해제:
- printf("a is %d, b is %f", *p_a, *p_b);는 p_a와 p_b가 가리키는 메모리의 값을 출력합니다.
- free(p_a);와 free(p_b);는 malloc을 통해 할당된 메모리를 해제합니다.
이 코드의 포인터 사용과 메모리 관리 방식은 C 프로그래밍에서 매우 중요한 부분이며, 포인터를 이해하고 올바르게 사용하는 것이 필수적입니다. 포인터가 가리키는 주소에 접근할 때는 * 연산자를 사용하고, 포인터 자체에 주소를 저장할 때는 그냥 포인터 변수 이름을 사용합니다. 이를 통해 메모리의 동적 할당과 관리를 효율적으로 수행할 수 있습니다.
...
5. 연결 리스트에서 노드의 삽입과 삭제
...
6. 연결 리스트의 여러 가지 연산 프로그램
내가 처음 C 배울 때 제일 빡쳤던 점. 책 마다 변수나 자료형에 애스터리스크를 완전 지 맘대로 붙이고 있었던 거.
앞에서는 *p라고 했다가 뒤에 보면 int* p가 되어 있다가 이런 점이 정말 굉장히 초보를 피로하고 혼란스럽게 했다.
교재에서 지금 부분에서도 이런 문제가 좀 있어 정리를 하자면
...
C 언어에서 포인터를 선언할 때, 별표(*)는 변수 이름 앞이나 자료형 뒤에 붙을 수 있습니다. 별표는 포인터 변수를 선언하는 데 사용되며, 그 위치는 주로 개발자의 선호나 코딩 스타일에 따라 다릅니다.
예를 들어, 다음 선언들은 모두 유효하며 같은 의미를 가집니다:
- int* p; // 별표가 자료형에 붙어있습니다.
- int *p; // 별표가 자료형과 변수 이름 사이에 있습니다.
- int * p; // 별표가 자료형과 변수 이름 사이에 있으며, 양쪽에 공백이 있습니다.
그러나 가독성과 일관성을 위해 일반적으로 int *p;의 형태를 선호합니다. 여기서 별표는 포인터 변수 p에 가깝게 위치하여 p가 포인터임을 분명히 나타냅니다. 이 방식은 포인터가 무엇을 가리키는지 (변수인지, 자료형인지) 명확하게 할 때 유용합니다.
이러한 스타일의 차이는 코드의 동작에 영향을 주지 않지만, 일반적으로 팀 내부 또는 프로젝트의 코딩 규칙에 따라 일관된 스타일을 사용하는 것이 좋습니다.
...
6. 연결 리스트의 노드 삽입
...
C 코드로 보니까 뭔가 이게 수도 코드(Pseudocode)인지 진짜 C 코드인지 사람 헷갈리는 상황이 계속 생기네.
'방송대 컴퓨터과학과 > 자료구조' 카테고리의 다른 글
| 방송대 자료구조 교재 요약 제7 장 - 트리 (0) | 2024.05.01 |
|---|---|
| 방송대 자료구조 교재 요약 제6 장 - 연결 리스트의 응용 (0) | 2024.05.01 |
| 방송대 자료구조 교재 요약 제4 장 - 큐 (0) | 2024.04.30 |
| 방송대 자료구조 교재 요약 제3 장 - 스택 (0) | 2024.04.29 |
| 방송대 자료구조 교재 요약 제2 장 - 배열 (0) | 2024.04.29 |
