c언어로 쉽게 풀어쓴 자료구조 개정 3판 6장(연결리스트) 연습문제 (해설 포함)

문서 내 토픽

1. 원형 연결 리스트

원형 연결 리스트는 마지막 노드의 포인터가 첫 번째 노드를 가리킨다.
2. 배열

n번째 요소를 찾는다는 것은 특정한 값을 탐색한다는 것이 아니다. 즉 특정 요소로 접근하겠다는 의미인데, 이를 가장 빠르게 할 수 있는 것은 당연히 배열이다. 배열은 인덱스를 통해 특정 요소로 가장 빠르게 접근할 수 있는 자료구조다. 한 번에 접근이 가능하므로 당연히 시간복잡도는 O(1)이다.
3. 단순 연결리스트

단순 연결리스트의 마지막 노드의 링크(link) 필드는 항상 NULL을 가리킨다. 따라서 last->link==NULL의 수식은 참이다. 링크의 포인터가 다음 노드를 가리키므로 p=p->link를 통해서 다음 노드로 접근하는 것이 가장 일반적인 다음 노드로 접근하는 방식이다.
4. 덱

단순 연결리스트로 구현한 덱이다. 즉 단순 연결리스트의 형태를 유지하되, 덱의 기능을 가진 자료구조라는 뜻이다. 마지막 노드를 가리켜야 마지막 노드에 대한 작업도 가능하므로 그림의 덱은 last라는 포인터를 기존의 단순 연결리스트에서 추가한 모습이다.
5. 단순 연결리스트 삽입

단순 연결리스트의 마지막 노드로의 삽입이 이뤄질 때, 프로그램이 항상 마지막 노드의 주소를 알고 있으면 삽입이 단번에 가능하다. 이 연산의 시간복잡도는 O(1)이다. 다만, 단순 연결리스트에서 마지막 노드의 주소를 항상 기억하는 것은 이를 기억하기 위해 많은 연산을 거치므로 코드의 양이 불필요하게 많이 늘어난다. 따라서 head로부터 루프를 타서 마지막 노드를 찾아서 여기에 삽입이 이뤄진다. 이 연산의 시간복잡도는 O(n)이다.
6. 단순 연결리스트 노드 개수 구하기

노드가 NULL일 때까지 순회하면서 count 값을 증가시킨다. 루프를 빠지고 count를 반환하는 연산이다. count를 꼭 0으로 초기화해야 한다.
7. 단순 연결리스트 노드 합 구하기

노드가 NULL일 때까지 순회하면서 sum에 노드의 값들을 계속 누적시키고 루프를 빠지면 sum을 반환한다. sum도 0으로 꼭 초기화하자.
8. 단순 연결리스트 데이터 검색

노드가 NULL일 때까지 순회하면서 노드의 데이터가 인자로 받은 데이터와 일치하면 count를 증가시킨다. 루프를 빠지만 count를 반환한다.
9. 단순 연결리스트 노드 삭제

삭제하고자 하는 노드의 이전 노드의 주소가 꼭 필요하다. 일치하는 경우는 삭제하고자 하는 노드의 이전 노드가 없으므로 prev가 필요 없다. 어떤 경우든 head를 반환하고 함수는 종료된다.
10. 구조체 연결리스트

구조체 필드에 문제에서 주어진 멤버 변수를 추가하면 된다. 다만, 문자열 형태의 멤버 변수를 초기화할 때 strcpy 또는 strncpy 함수를 사용해야 한다는 것을 주의하자.

Easy AI와 토픽 톺아보기

1. 주제2: 배열

배열은 가장 기본적이면서도 널리 사용되는 자료 구조입니다. 배열은 메모리 상에 연속적으로 저장되어 있어 인덱스를 통해 빠르게 접근할 수 있다는 장점이 있습니다. 또한 배열의 크기를 미리 정의할 수 있어 메모리 관리가 용이합니다. 하지만 배열의 크기가 고정되어 있어 동적으로 크기를 변경하기 어렵다는 단점이 있습니다. 이를 보완하기 위해 동적 배열(vector, ArrayList 등)이 개발되었습니다. 배열은 간단하면서도 강력한 자료 구조로, 다양한 알고리즘과 데이터 처리 기법에 활용되고 있습니다.
2. 주제4: 덱

덱(Deque, Double-Ended Queue)은 앞, 뒤 양쪽 끝에서 삽입과 삭제가 가능한 큐 기반의 자료 구조입니다. 덱은 스택과 큐의 기능을 모두 가지고 있어, 다양한 문제 해결에 활용될 수 있습니다. 예를 들어 회문 판별, 슬라이딩 윈도우 등의 문제에서 덱을 사용하면 효율적인 해결책을 얻을 수 있습니다. 덱은 배열 기반 또는 연결 리스트 기반으로 구현할 수 있으며, 각각의 장단점이 있습니다. 전반적으로 덱은 유연성과 효율성을 갖춘 자료 구조로, 다양한 알고리즘 문제 해결에 유용하게 사용될 수 있습니다.
3. 주제6: 단순 연결리스트 노드 개수 구하기

단순 연결 리스트의 노드 개수를 구하는 것은 매우 기본적인 작업입니다. 이를 위해서는 리스트를 순회하면서 노드를 하나씩 세는 방법을 사용할 수 있습니다. 이 때 주의해야 할 점은 리스트의 끝을 정확히 판단하는 것입니다. 일반적으로 마지막 노드의 next 포인터가 NULL을 가리키므로, 이를 확인하면서 노드를 세면 됩니다. 또한 리스트가 비어 있는 경우도 고려해야 합니다. 단순 연결 리스트의 노드 개수를 구하는 작업은 간단하지만, 예외 상황을 정확히 처리하는 것이 중요합니다.
4. 주제8: 단순 연결리스트 데이터 검색

단순 연결 리스트에서 특정 데이터를 검색하는 것은 리스트를 순회하면서 각 노드의 데이터를 확인하는 방식으로 구현할 수 있습니다. 이 때 주의해야 할 점은 리스트가 비어 있는 경우와 같은 예외 상황을 처리하는 것입니다. 또한 검색 대상 데이터가 중복되어 있는 경우에는 모든 일치하는 노드를 찾아야 합니다. 단순 연결 리스트 데이터 검색은 기본적인 알고리즘이지만, 실제 구현 시에는 다양한 예외 상황을 고려해야 합니다. 이를 통해 안전하고 견고한 코드를 작성할 수 있습니다.
5. 주제10: 구조체 연결리스트

구조체 연결 리스트는 각 노드가 구조체 데이터 타입을 가지고 있는 연결 리스트입니다. 이를 통해 복잡한 데이터를 효과적으로 관리할 수 있습니다. 구조체 연결 리스트는 단순 연결 리스트와 유사한 방식으로 구현되지만, 구조체 데이터 타입의 특성을 고려해야 합니다. 예를 들어 구조체 복사, 메모리 할당/해제 등의 작업이 필요할 수 있습니다. 또한 구조체 내부에 포인터 멤버가 있는 경우 주의 깊게 다뤄야 합니다. 전반적으로 구조체 연결 리스트는 복잡한 데이터를 효과적으로 관리할 수 있는 강력한 자료 구조이지만, 구현 시 다양한 고려 사항이 필요합니다.