2023. 12. 1. 12:40ㆍ프로그래밍 공부/OOP
연결리스트(linked list): 포인터를 사용하여 작성한 리스트
연결리스트는 크기가 고정되어 있는 것이 아니라 프로그램이 실행되는 동안 커지고 축소될 수 있다.
트리는 포인터를 사용하여 작성한 또 다른 종류의 자료 구조이다.
이 장에서는 이러한 자료 구조를 작성하기 위한 포인터의 사용에 대해 소개한다.
표준 템플릿 라이브러리(Standard Template Library, STL)에서 이와 유사한 자료 구조를 미리 정의된 버전으로 제공한다.
STL은 19장에서 다룬다.
STL에서 미리 정의된 자료 구조를 사용하는 것이 정의하는 것보다 더 합리적인 경우가 많다.
그러나 포인터를 사용하여 자신의 데이터 구조를 정의해야 하는 경우가 있다.
또한 이 자료를 통해 STL이 어떻게 정의되었는지 이해할 수 있으며 널리 사용되는 기본 자료를 소개할 것이다.
연결된 자료 구조는 new 연산자로 생성되는 동적 변수를 사용하여 구조를 생성한다.
연결된 자료 구조는 이러한 변수를 연결하기 위해 포인터를 사용한다.
이를 통해 메모리를 관리하는 방법을 비롯하여 자료 구조를 구축하고 관리하는 방법을 완벽하게 제어할 수 있다.
이를 통해 때로는 작업을 더 효율적으로 수행할 수 있다.
예를 들어 정렬된 배열보다 정렬된 연결 리스트에 값을 삽입하는 것이 더 쉽고 빠르다.
이 장에서 논의하는 데이터 구조는 기본적으로 세 가지 방법으로 처리할 수 있다:
1. 전역 함수와 struct를 모든 public한 것과 함께 사용하는 C-스타일 접근법
2. 모든 멤버 변수가 private 클래스 사용 및 접근자와 설정자 사용
3. friend 클래스 사용(또는 private 또는 protected 상속 또는 지역적으로 정의된 클래스 등 유사)
세 가지 방법 모두에 대한 예를 제시한다.
방법 1을 사용하여 연결리스트를 소개한다.
그런 다음 기본 연결리스트에 대한 자세한 내용을 제시하고
방법 2를 사용하여 스택 및 큐 자료 구조를 소개한다.
friend 클래스(방법 3)를 사용하여 큐 템플릿 클래스에 대한 대체 정의를 제시하고
friend 클래스(방법 3)를 사용하여 트리 템플릿 클래스를 제시한다.
이렇게 하면 각 접근 방식의 장점과 단점을 확인할 수 있다.
개인적으로 friend 클래스를 사용하는 것을 선호하지만 각 방법에는 옹호자가 있다.
17.1절부터 17.3절까지는 13장부터 15장까지의 자료(재귀, 상속, 다형성)를 사용하지 않는데, 한 가지 작은 예외가 있다.
15장의 조언에 따라 클래스 소멸자를 virtual이라는 수식어로 표시했다.
가상 함수에 대해 아직 읽지 않았다면(15장), 코드에 "virtual"이 없는 것처럼 행동할 수 있다.
이 장의 목적에 따라 "virtual"이 존재하는지 여부는 차이가 없다.
17.4절은 재귀(13장)를 사용하지만 14장과 15장은 사용하지 않는다.
17.1 노드 및 연결리스트
디스플레이 17.1의 하나의 다이어그램 - 연결 리스트: 동적 자료 구조(dynamic data structre)의 단순한 예
상자 - 노드(node): new 연산자를 사용하여 동적으로 생성된 struct나 클래스 형식의 변수이다. 포인터를 포함한다.
화살표 - 포인터(pointer): 다른 노드를 가리키킨다.
이 절에서는 연결 리스트를 구축하고 유지 관리하기 위한 기본 기법을 소개한다.
노드
노드의 구조
디스플레이 17.1과 같은 구조는 우리가 화살표로 연결된 상자로 그린 것들로 구성되어 있다.
상자 - 노드(node): 문자열 값 + 정수 + 같은 종류의 다른 노드를 가리키는 포인터
화살표 - 포인터(pointer): 노드 안에 있는 개별 항목(예를 들어, 10개 또는 "rolls")이 아니라 전체 노드를 가리킨다.
노드 형식 정의
노드는 C++에서 struct 또는 클래스로 구현된다.
예시)
디스플레이 17.1에 표시된
형식의 노드에 대한 struct 형식 정의와
이러한 노드에 대한 포인터에 대한 형식 정의는
다음과 같을 수 있다:
struct ListNode
{
string item;
int count;
ListNode *link;
}
Typedef ListNode* ListNodePtr;
형식 정의의 순서가 중요하다.
ListNodePtr의 정의에 사용되기 때문에
ListNode의 정의가 우선되어야 한다.
디스플레이 17.1에서
head라고 표시된 상자: 노드를 가리킬 수 있는 포인터 변수 (노드가 아니다!)
포인터 변수 head는 다음과 같이 선언된다:
ListNodePtr head;
일부 불법적인 형태의 순환을 피하기 위해 형식 정의를 지시했지만
struct 형식 ListNode의 이전 정의는 여전히 순환이다.
ListNode 형식의 정의는 멤버 변수 link를 정의할 때 ListNode 형식이라는 이름을 사용한다.
C++에서 허용되는 이 특별한 순환성에는 아무 문제가 없다.
이러한 정의가 논리적으로 모순성이 없다는 것을 나타내는 하나의 지표는
그러한 구조를 나타내는 그림을 그릴 수 있다는 것이다.
노드 데이터 바꾸기
이제 struct 내부에 포인터가 있고 포인터를 포함하는 struct를 가리키는 포인터가 있다.
그런 경우에는 구문이 개입될 수 있지만,
모든 경우에 구문은 포인터와 구조체에 대해 설명한 몇 가지 규칙을 따른다.
예시)
선언문이 표시된 대로이고,
상황이 디스플레이 17.1의 다이어그램과 같으며
첫 번째 노드의 숫자를 10에서 12로 변경하려고 한다고 가정한다.
이를 수행하는 한 가지 방법은 다음 문장과 같다:
(*head).count = 12;
할당 연산자의 왼쪽에 있는 식은 약간의 설명이 필요할 수 있다.
변수 head는 포인터 변수이다.
따라서 *head는 "rolls"과 정수 10을 포함하는 노드(동적 변수)를 가리킨다.
*head로 지칭되는 이 노드는 struct이며,
정수의 값을 포함하는 이 struct의 멤버 변수는 count라고 한다.
따라서 (*head.count)는 첫 번째 노드에 있는 int 변수의 이름이다.
*head 주변의 괄호는 선택 사항이 아니다.
점 연산 전에 역참조 연산인 *를 수행하기를 원한다.
그러나 점 연산자는 역참조 연산자 *보다 우선순위가 높으므로, 괄호가 없으면 점 연산이 먼저 수행된다(오류가 발생함).
다음 단락에서는 괄호에 대한 이러한 걱정을 피할 수 있는 바로 가기 표기법을 설명한다.
디스플레이 17.1 노드와 포인터
-> 연산자
C++에는 구조체나 클래스의 멤버를 지정하기 위한 표기를 단순화하기 위해 포인터와 함께 사용할 수 있는 연산자가 있다.
10장에서는 화살표 연산자 ->를 소개했지만 지금까지 광범위하게 사용하지는 않았다. 따라서 리뷰가 진행 중이다.
화살표 연산자: 역참조 연산자, * 및 점 연산자의 동작을 결합하여 주어진 포인터로 가리키는 동적 구조체 또는 클래스 객체의 멤버를 지정한다.
예시)
첫 번째 노드에서 번호를 변경하기 위한 이전 할당문은 다음과 같이 간단히 적을 수 있다
head->count = 12;
이번 할당문과 이전 할당문은 같은 의미지만, 이것은 일반적으로 사용되는 양식이다.
첫 번째 노드의 문자열은 다음 문장으로 "rolls"에서 "bagels"로 변경할 수 있다:
head->item = "bagels";
목록의 첫 번째 노드에 대한 이러한 변경 결과는 디스플레이 17.2에 도식화되어 있다.
디스플레이 17.2 노드 데이터 접근하기
head->count = 12;
head->item = "bagels";
Before
After
화살표 연산자, ->
화살표 연산자 ->: 포인터 변수로 가리키는 구조의 멤버 또는 클래스 객체의 멤버를 지정한다.
구문은
Pointer_Variable->Member_Name
Pointer_Variable이 가리키는 struct 또는 클래스 객체의 멤버를 나타낸다.
Member_Name은(는) 참조할 멤버이다.
예시)
struct Record
{
int number;
char grade;
};
다음은 Record 형식의 동적 변수를 만들고
동적 struct 변수의 멤버 변수를 2001 및 'A'로 설정한다:
Record *p;
p = new Record;
p->number = 2001;
p->grade = 'A';
NULL
디스플레이 17.2에 있는 목록의 마지막 노드에 있는 포인터 멤버를 보자.
이 마지막 노드에는 포인터가 있어야 하는 곳에 NULL이라는 단어가 쓰여 있다.
디스플레이 17.1에서 우리는 이 위치를 "end marker"라는 문구로 채웠지만 "end marker"는 C++ 표현이 아니다.
C++ 프로그램에서 우리는 상수 NULL을 마커로 사용하여
연결 리스트의 끝(또는 다른 종류의 연결된 자료 구조의 끝)을 표시한다.
NULL은 일반적으로 서로 다른 두 가지 목적으로 사용된다.
1. NULL은 어떤 값도 가지지 않을 포인터 변수에 값을 주기 위해 사용된다.
그러면 NULL은 메모리 위치의 주소가 아니므로 메모리에 대한 부주의한 참조를 방지할 수 있다.
2. 두 번째 사용 범주는 엔드 마커(end marker)이다.
프로그램은 디스플레이 17.2와 같이 노드 목록을 단계적으로 수행할 수 있으며
프로그램이 NULL을 포함하는 노드에 도달하면 목록의 끝에 도달했음을 알 수 있다.
NULL은 0이다
10장에서 언급한 것처럼 상수 NULL은 실제로 숫자 0이지만
포인터 변수에 할당할 수 있는 특수 목적 값을 의미한다는 것을 분명히 하기 위해
NULL로 생각하고 철자를 쓰는 것을 선호한다.
식별자 NULL의 정의는 <iostream> 및 <cstddef>와 같은 여러 표준 라이브러리에 있으므로
NULL을 사용할 때는 <iostream>, <cstddef> 또는 다른 적절한 라이브러리와 함께 include 지시문을 사용해야 한다.
NULL의 정의는 C++ 전처리기가 처리하며 NULL을 0으로 대체한다.
따라서 컴파일러는 실제로 "NULL"을 보지 않으므로 네임스페이스 문제가 없으므로 NULL에 대해 명령어를 사용할 필요가 없다.
다음과 같이 할당 연산자를 사용하여 포인터를 NULL로 설정할 수 있다.
여기서 호출되는 포인터 변수를 선언하고 NULL로 초기화한다:
double *there = NULL;
상수 NULL은 모든 포인터 형식의 포인터 변수에 할당할 수 있다.
NULL
NULL은 특별한 상수 값으로, 그렇지 않으면 값을 갖지 않을 포인터 변수에 값을 부여하는 데 사용된다.
NULL은 어떤 형식의 포인터 변수에도 할당될 수 있다.
식별자 NULL은
헤더 파일 <cstddef>가 있는 라이브러리와
헤더 파일 <iostream>이 있는 라이브러리를 포함한
여러 라이브러리에서 정의된다.
상수 NULL은 실제로 숫자 0이지만,
이것을 NULL로 생각하고 철자를 쓰는 것을 선호한다.
인수로써 연결 리스트
항상 하나의 포인터 변수가 연결 리스트의 맨 앞을 가리켜야 한다.
이 포인터 변수는 연결 리스트의 이름을 붙이는 방법이다.
연결 리스트을 인수로 삼는 함수를 작성할 때
이 포인터(연결 리스트의 맨 앞을 가리킴)가 연결 리스트의 인수로 사용될 수 있다.
연결 리스트
연결 리스트
디스플레이 17.1과 같은 목록을 연결 리스트라고 한다.
연결 리스트(linked list): 각 노드에 목록의 다음 노드를 가리키는 포인터인 멤버 변수가 있는 노드의 목록
헤드
헤드(head): 연결 리스트의 첫 번째 노드
head: 첫 번째 노드를 가리키는 포인터 변수의 이름
head라고 이름 지어진 포인터는 목록의 헤드가 아니라 단지 그것을 가리킨다.
마지막 노드
마지막 노드에는 특별한 이름이 없지만 멤버 포인터 변수의 값으로 NULL이 있다는 특별한 속성이 있다.
노드가 마지막 노드인지 여부를 테스트하려면 노드의 포인터 변수가 NULL과 같은지 여부만 테스트하면 된다.
노드 형식 정의
이 절에서 우리의 목표는 연결된 목록을 조작하기 위한 몇 가지 기본 함수를 작성하는 것이다.
다양성과 표기의 단순화를 위해
노드에 대해 디스플레이 17.2에서 사용된 것보다 더 간단한 형식의 데이터를 사용할 것이다.
이 노드들은 정수와 포인터로만 구성될 것이다.
그러나 우리는 한 가지 의미에서 노드를 더 복잡하게 만들 것이다.
우리는 그것들을 단순한 구조가 아니라 클래스의 객체로 만들 것이다.
우리가 사용할 노드와 포인터 형식의 정의는 다음과 같다:
class IntNode
{
public:
IntNode( ) {}
IntNode( int theData, IntNode* theLink)
: data(theData), link(theLink) {}
IntNode* getLink( ) const { return link; }
int getData( ) const { return data; }
void setData( int theData) { data = theData; }
void setLink(IntNode* pointer) { link = pointer; }
private:
int data;
IntNode *link;
};
typedef IntNode* IntNodePtr;
클래스 IntNode의 모든 멤버 함수는 인라인 정의를 가질 수 있을 정도로 간단하다.
클래스 IntNode에 대한 2개의 매개변수를 가진 생성자를 주목하자.
이를 통해 지정된 정수를 데이터로 사용하고 지정된 링크 멤버를 가진 노드를 만들 수 있다.
예시)
p1이 n1을 가리키는 경우,
다음은 p2가 가리키는 새 노드를 생성하여
이 새 노드가 데이터 42를 갖고 n1을 가리키는 링크 멤버를 갖는다:
IntNodePtr p2 = new IntNode(42, p1);
이 노드 형식으로 연결 리스트를 생성하고 조작하기 위한 몇 가지 기본 함수를 도출한 후
노드 형식과 함수를 템플릿 버전으로 변환하여
노드에 어떤 유형의 데이터를 저장하는 작업을 수행한다.
하나의 노드를 가진 연결 리스트(a one-node linked list)
준비 운동으로, 이러한 형식의 노드로 연결 리스트의 시작을 어떻게 구성할 수 있는지 알아보겠다.
먼저 연결 리스트의 맨 앞을 가리키는 head라는 포인터 변수를 선언한다:
IntNodePtr head;
첫 번째 노드를 생성하기 위해
연산자 new를 사용하여 연결 리스트의 첫 번째 노드가 될 새로운 동적 변수를 생성한다:
head = new IntNode;
그런 다음 이 새 노드의 멤버 변수에 값을 부여한다:
head->setData(3);
head->setLink(NULL);
이 노드는 연결 리스트의 마지막 노드이자 연결 리스트의 첫 번째 노드이므로
이 노드의 포인터 멤버는 NULL로 설정된다.
이 단계에서 연결 리스트는 다음과 같다:
그것은 우리가 해야 할 일보다 더 많은 일이었다.
두 개의 매개변수를 가진 IntNode 생성기를 사용하면
훨씬 더 쉽게 하나의 노드를 가진 연결 리스트를 만들 수 있다.
지금 그림에서 하나의 노드를 가진 연결 리스트를 얻는 더 쉬운 방법은 다음과 같다:
head = new IntNode(3, NULL);
알고 보니, 우리는 항상 IntNode에 대해
이 두 개의 인수를 가진 생성자를 사용하여 새로운 노드를 생성할 것이다.
심지어 많은 프로그램들은
각 멤버 변수에 대한 값을 지정하지 않고 노드를 생성하는 것이 불가능하도록
IntNode의 정의에서 0개의 인수를 가진 생성자를 생략할 것이다.
우리의 한 개의 노드를 가진 연결 리스트는 특별한 방식으로 구축되었다.
더 큰 연결 리스트를 가지려면 프로그램이 체계적인 방식으로 노드를 추가할 수 있어야 한다.
다음은 연결 리스트에 노드를 삽입하는 한 가지 간단한 방법을 설명한다.
리스트 맨 앞에 노드 삽입
이 절에서는 연결 리스트에 이미 하나 이상의 노드가 포함되어 있다고 가정하고
다른 노드를 추가하는 함수를 개발한다.
삽입 함수의 첫 번째 매개변수는 연결 리스트의 맨 앞을 가리키는 포인터 변수,
즉 연결 리스트의 첫 번째 노드를 가리키는 포인터 변수에 대한 call-by-reference 매개변수가 될 것이다.
다른 매개변수는 새 노드에 저장할 번호를 줄 것이다.
삽입 기능에 대한 함수 선언은 다음과 같다:
void headInsert(IntNodePtr& head, int theData);
연결 리스트에 새 노드를 삽입하기 위해
함수는 새 연산자와 IntNode에 대한 두 개의 인수를 가진 생성자를 사용힌다.
새 노드는 theData를 데이터로 가지며
그것의 연결 멤버가 연결 리스트의 첫 번째 노드를 가리킨다.
동적 변수는 다음과 같이 생성된다:
new IntNode(theData, head)
우리는 포인터 헤드가 이 새로운 노드를 가리키도록 하고,
그래서 함수 본체는 간단히
{
head = new IntNode(theData, head);
}
디스플레이 17.3은 동작의 다이어그램을 포함한다
head = new IntNode(theData, head);
데이터가 12일 때 전체 함수 정의는 디스플레이 17.4에 나와 있다.
빈 리스트
리스트에 아무것도 포함되어 있지 않을 가능성을 허용하고자 할 것이다.
예를 들어, 쇼핑 목록에는 이번 주에 살 물건이 없기 때문에 아무것도 포함되어 있지 않을 수도 있다.
빈 리스트(empty list): 아무것도 포함되어 있지 않은 리스트
연결 리스트은 리스트의 헤드 부분을 가리키는 포인터의 이름을 붙여서 이름을 짓지만, 빈 리스트는 헤드 부분이 없다.
빈 리스트를 지정하려면 NULL 값을 사용한다.
포인터 변수 head가 연결된 목록의 헤드 부분을 가리키도록 되어 있고 리스트가 비어 있음을 나타내고자 한다면,
head 부분의 값을 다음과 같이 설정하라:
head = NULL;
연결 리스트를 조작하기 위한 함수를 설계할 때마다
빈 리스트에서 작동하는지 항상 확인해야 한다.
그렇지 않으면 빈 리스트에 대한 특수한 경우를 추가할 수 있다.
빈 리스트에 적용할 함수를 설계할 수 없다면
빈 리스트를 다른 방식으로 처리하거나 완전히 피하도록 프로그램을 설계해야 한다.
다행히 빈 리스트는 종종 다른 리스트와 마찬가지로 취급될 수 있다.
예를 들어, 디스플레이 17.4의 함수 headInsert는 모델로 빈 리스트가 아닌 것으로 설계했지만
검사를 하면 빈 리스트에서도 작동한다는 것을 알 수 있다.
디스플레이 17.3 연결리스트의 헤드에 노드 추가
삽입 전 연결리스트
new IntNode(12, head)
에 의해 생성된 노드
연결 리스트 실행 후
head = new IntNode(12, head);
디스플레이 17.4 연결 리스트에 노드 추가 기능
노드와 포인터 타입 정의
class IntNode
{
public:
IntNode( ) {}
IntNode( int theData, IntNode* theLink)
: data(theData), link(theLink) {}
IntNode* getLink( ) const { return link; }
int getData( ) const { return data; }
void setData( int theData) { data = theData; }
void setLink(IntNode* pointer) { link = pointer; }
private:
int data;
IntNode *link;
};
typedef IntNode* IntNodePtr;
연결 리스트 맨 앞에 노드를 추가하는 함수
함수 선언
void headInsert(IntNodePtr& head, int theData);
//Precondition: The pointer variable head points to
//the head of a linked list .
//Postcondition: A new node containing theData
//has been added at the head of the linked list .
함수 정의
void headInsert(IntNodePtr& head, int theData)
{
head = new IntNode(theData, head);
}
연결 리스트 가운데에 노드를 추가하는 함수
함수 선언
void insert(IntNodePtr afterMe, int theData);
//Precondition: afterMe points to a node in a linked list .
//Postcondition: A new node containing theData
//has been added after the node pointed to by afterMe .
함수 정의
void insert(IntNodePtr afterMe, int theData)
{
afterMe->setLink( new IntNode(theData, afterMe->getLink( )));
}
함정: 노드 손실
새로운 노드의 멤버 변수를 설정하기 위해 0개의 인수를 가진 생성자를 사용하여
headInsert(Display 17.4)에 대한 함수 정의를 작성하고자 할 수 있다.
시도할 경우 다음과 같이 함수를 시작할 수 있다:
head = new IntNode;
head->setData(theData);
이 시점에서 새 노드가 구축되고
올바른 데이터가 포함되며
포인터 head가 이 모든 것을 가리킨다.
이 새 노드에서 포인터 멤버를 설정하여 연결 리스트의 나머지 부분을 이 노드에 연결하면
이전에 연결 리스트의 첫 번째 노드를 가리킬 수 있다.
물음표 대신 어떤 포인터를 배치할지만 알면 다음 작업을 수행할 수 있다:
head->setLink(?);
디스플레이 17.5는 새로운 데이터 값이 12일 때의 상황을 보여주며 문제를 보여준다.
만약 계속 이런 식으로 진행한다면 15를 포함하는 노드를 가리키는 것은 아무것도 없을 것이다.
프로그램이 이 노드를 가리키는 명명된 포인터가 없으므로
(또는 그 노드로 확장되는 포인터의 연쇄를 가리키는)
프로그램이 이 노드를 참조할 수 있는 방법은 없다.
노드와 이 노드 아래의 모든 노드가 유실된다.
프로그램은 이 노드들 중 어느 것도 가리키는 포인터를 만들 수 없으며,
이 노드들의 데이터에 접근하거나 그 노드들에 다른 어떤 것도 할 수 없다.
단순히 노드들을 참조할 방법이 없다.
이러한 상황은 프로그램이 진행되는 동안 메모리를 묶어놓는다.
노드들을 잃는 프로그램은 때때로 메모리 손실(memory leak)이 있다고 말한다.
메모리 손실이 심하면 프로그램이 메모리를 다 써버려 비정상적으로 종료될 수 있다.
더 심각한 것은 일반 사용자 프로그램의 메모리 손실(잃어버린 노드)은 드문 상황에서 운영 체제를 붕괴시킬 수 있다.
이러한 손실된 노드를 피하기 위해서 프로그램은
항상 어떤 포인터가 연결 리스트의 맨 앞을 가리키도록 유지해야 하며,
대개 포인터가 head와 같은 포인터 변수로 있어야 한다.
디스플레이 17.5 노드 손실
연결 리스트 삽입 전
head = new IntNode;
head->setData(theData);
실행 후 상황
리스트 내 노드 삽입 및 제거
리스트의 중간에 삽입하기
우리는 다음으로 연결 리스트에서 지정된 위치에 노드를 삽입하는 함수를 설계한다.
만약 당신이 숫자나 알파벳 같은 특정한 순서로 노드를 원한다면, 단순히 목록의 처음이나 끝에 노드를 삽입할 수 없다.
따라서 우리는 연결 리스트에서 지정된 노드 뒤에 노드를 삽입하는 함수를 설계할 것이다.
다른 함수나 프로그램 부분이
연결 리스트의 일부 노드를 가리키는 afterMe 뒤에 호출된 포인터를
올바르게 배치했다고 가정한다.
우리는 새로운 노드를 디스플레이 17.6과 같이 afterMe 뒤에 지정된 노드 뒤에 배치하기를 원한다.
어떤 종류의 데이터를 가진 노드에도 동일한 기법이 적용되지만,
구체적으로 우리는 이전 하위 섹션과 동일한 형식의 노드를 사용하고 있다.
형식 정의는 디스플레이 17.4에 나와 있다.
우리가 정의하고자 하는 함수에 대한 함수 선언은 다음과 같다:
void insert(IntNodePtr afterMe, int theData);
//Precondition: afterMe points to a node in a linked list .
//Postcondition: A new node containing theData
//has been added after the node pointed to by afterMe .
새로운 노드는 기본적으로 리스트의 헤드(시작)에 노드를 추가하는 것과 같은 방식으로 리스트 내부에 삽입된다.
유일한 차이점은 포인터 head 대신 afterMe->link 뒤에 포인터를 사용한다는 것이다.
삽입은 다음과 같이 수행된다:
afterMe->setLink(new IntNode(theData, afterMe->getLink( )));
theData가 5인 세부 정보는 디스플레이 17.6에 나와 있으며
최종 함수 정의는 디스플레이 17.4에 나와 있다.
마지막에 삽입
함수 insert 코드를 읽어보면
afterMe가 가리키는 노드가 리스트의 마지막 노드일지라도
올바르게 작동하는 것을 확인할 수 있다.
그러나 insert는 연결 리스트의 처음에 노드를 삽입하는 데에는 작동하지 않다.
디스플레이 17.4에 주어진 함수 headInsert를 사용하여 리스트의 처음에 노드를 삽입할 수 있다.
배열과 비교
함수 insert를 사용하면 연결 리스트를 숫자나 알파벳 순서로 유지하거나 다른 순서로 유지할 수 있다.
두 개의 포인터를 조정하기만 하면 새로운 노드를 올바른 위치에 압축할 수 있다.
연결 리스트의 길이나 목록의 위치에 상관없이 이것은 사실이다.
대신 배열을 사용하면
새로운 값을 올바른 위치에 배치하기 위해
배열의 많은 부분, 그리고 극단적인 경우에는 배열의 모든 부분을 복사해야 한다.
afterMe 다음에 포인터를 배치하는 데 드는 오버헤드에도 불구하고,
연결 리스트에 삽입하는 것이 배열에 삽입하는 것보다 더 효율적인 경우가 많다.
디스플레이 17.6 연결 리스트 가운데에 삽입
new IntNode(5, afterMe->getLink( ));
에 의해 생성된 노드.
afterMe->getLink()가 강조되었다.
afterMe->setLink(new IntNode(theData, afterMe->getLink( )));
의 최종 결과
노드 제거하기
연결 리스트에서 노드를 제거하는 것도 매우 쉽다.
디스플레이 17.7은 이 방법을 보여준다.
일단 포인터를 놓고 버리면, 노드를 제거하는 데 필요한 모든 것은 다음 문장이다:
before->setLink(discard->getLink( ));
이 정도면 노드를 연결 리스트에서 제거하기에 충분하다.
그러나 이 노드를 다른 용도로 사용하지 않는 경우
노드를 소멸하고 재사용에 사용하는 메모리를 반환해야 한다.
다음과 같이 delete하기 위해 호출을 해서 이 작업을 수행할 수 있다:
delete discard;
10장에서 언급했듯이 동적 변수의 메모리는 freestore이라고 하는 메모리 영역에 저장된다.
freestore은 무제한이 아니기 때문에
프로그램에서 동적 변수(노드)가 더 이상 필요하지 않을 때는
delete 연산자를 사용하여 재사용하기 위해 이 메모리를 반환해야 한다.
이어지는 설명에 delete 연산자에 대한 리뷰가 포함되어 있다.
delete 연산자
delete 연산자는 동적 변수를 제거하고 동적 변수가 사용한 메모리를 freestore에 반환한다.
그러면 메모리를 재사용하여 새로운 동적 변수를 만들 수 있다.
예를 들어, 포인터 변수 p가 가리키는 동적 변수를 제거하는 것은 다음과 같다:
delete p;
delete 호출 후에 표시된 p와 같이 포인터 변수의 값이 정의되지 않다.
디스플레이 17.7 노드 제거하기
before->setLink(discard->getLink( ));
delete discard;
함정: 동적 자료 구조에 할당 연산자 사용
head1과 head2가 포인터 변수이고 head1이 연결 리스트의 헤드 노드를 가리킬 경우,
다음은 head2가 동일한 head 노드를 가리킴으로써 동일한 연결 리스트를 가리킨다:
head2 = head1;
그러나 연결 리스트는 두 개가 아니라 하나만 있다는 것을 기억해야 한다.
만약 hand1이 가리키는 연결 리스트를 바꾼다면
hand2가 가리키는 연결 리스트도 같은 연결 리스트이기 때문에
당신은 또한 hand2가 가리키는 연결 리스트를 바꿀 것이다.
head1이 연결 리스트를 가리키고
head2가 이 연결 리스트의 두 번째, 동일한 복사본을 가리키도록 하려면
이전 할당문이 작동하지 않는다.
대신 전체 연결 리스트 노드를 노드별로 복사해야 한다.
연결 리스트 검색
search
다음으로 우리는 특정 노드를 찾기 위해 연결 리스트를 검색하는 함수를 설계할 것이다.
우리는 이전 하위 섹션에서 사용했던 것과 동일한 노드 유형인 IntNode를 사용할 것이다.
(노드와 포인터 유형의 정의는 디스플레이 17.4에 나와 있다.)
우리가 설계하는 함수는 연결 리스트와 우리가 찾고자 하는 정수라는 두 가지 인수를 가질 것이다.
함수는 해당 정수를 포함하는 첫 번째 노드를 가리키는 포인터를 반환할 것이다.
만약 어떤 노드도 정수를 포함하지 않는다면 함수는 NULL을 반환할 것이다.
이 방법으로 프로그램은 함수가 NULL과 동일하지 않은 포인터 값을 반환하는지 확인하여
int가 리스트에 있는지 테스트할 수 있다.
함수에 대한 함수 선언 및 헤더 코멘트는 다음과 같다:
IntNodePtr search(IntNodePtr head, int target);
//Precondition: The pointer head points to the head of a
//linked list. The pointer variable in the last node is NULL .
//If the list is empty, then head is NULL.
//Returns a pointer that points to the first node that contains the
//target. If no node contains the target, the function returns NULL .
target을 찾아 리스트를 이동하기 위해
here라고 불리는 포인터 변수를 사용할 것이다.
연결 리스트나 노드와 포인터로 구성된 모든 다른 자료 구조를 이동하는 유일한 방법은 포인터를 따르는 것이다.
따라서 여기서는 첫 번째 노드를 가리키는 것으로 시작하여
각 노드에서 포인터를 따라 노드에서 노드로 이동할 것이다.
이 기법은 디스플레이 17.8에 도표로 표시되어 있다.
빈 리스트는 우리의 논의를 방해할 만한 사소한 문제들을 포함하고 있으므로,
우리는 우선 연결 리스트에 적어도 하나의 노드가 포함되어 있다고 가정할 것이다.
나중에 우리는 다시 와서 빈 리스트에 대해서도 알고리즘이 작동하는지 확인할 것이다.
이 검색 기법은 다음과 같은 알고리즘을 산출한다:
Pseudocode for search Function
Make the pointer variable here point to the head node (that is, first node) of the linked list.
while ( here is not pointing to a node containing target and here is not pointing to the last node)
{
Make here point to the next node in the list.
}
if (the node pointed to by here contains target)
return here;
else
return NULL;
포인터 here를 다음 노드로 이동시키려면
우리가 사용할 수 있는 이름이 붙은 포인터의 관점에서 생각해야 한다.
다음 노드는 현재 here에 의해 가리키는 노드의 포인터 멤버가 가리키는 노드이다.
here에 의해 현재 가리키는 노드의 포인터 멤버는 다음 식에 의해 주어진다
here->getLink( )
여기서 다음 노드로 이동하려면
here을 변경하여 위 이름의 포인터가 가리키는 노드를 가리킨다.
따라서 다음은 포인터 here를 목록의 다음 노드로 이동한다:
here = here->getLink( );
디스플레이 17.8 연결리스트 검색하기
target is 6
1
2 Not here
3 Not here
4 Found
알고리즘 개선
이러한 조각들을 결합하면 검색 함수에 대한 알고리즘 의사 코드가 다음과 같이 개선된다:
here = head;
while (here->getData( ) != target && here->getLink( ) != NULL)
here = here->getLink( );
if (here->getData( ) == target)
return here;
else
return NULL;
while문의 부울식을 주목하자.
멤버 변수 here->getLink()가 NULL과 같은지 테스트하여
here가 마지막 노드를 가리키고 있는지 테스트한다.
빈 리스트
여전히 빈 리스트를 처리해야 한다.
이전 코드를 확인하면 빈 리스트에 문제가 있다는 것을 알 수 있다.
리스트가 비어 있으면 here은 NULL과 같으므로 다음 식을 정의할 수 없다:
here->getData( )
here->getLink( )
here가 NULL일 때, 어떤 노드도 가리키는 것이 아니므로 데이터 멤버나 링크 멤버가 없다.
그래서 우리는 빈 리스트의 특별한 경우를 만든다.
전체 함수 정의는 디스플레이 17.9에 나와 있다.
이중 연결 리스트
일반적으로 연결 리스트는 리스트를 아래로 한 방향으로만 이동시킬 수 있다.
이중 연결 리스트는 다음을 포함한다.
하나의 링크 - 다음 노드로 향하는 포인터
추가 링크 - 이전 노드로 향하는 포인터
이전 노드로 가는 링크가 코드를 단순화하는 경우도 있다.
예시)
리스트에서 노드를 제거하면
폐기하고자 하는 노드로 가는 노드를 기억하기 위한 before 변수가 더 이상 필요하지 않다.
도식적으로, 이중 연결 리스트는 디스플레이 17.10의 샘플 리스트처럼 보인다.
디스플레이 17.9 연결 리스트에서 노드 찾기 함수
함수 선언
IntNodePtr search(IntNodePtr head, int target);
//Precondition: The pointer head points to the head of a
//linked list. The pointer variable in the last node is NULL .
//If the list is empty, then head is NULL .
//Returns a pointer that points to the first node that contains the
//target. If no node contains the target, the function returns NULL .
함수 정의
//Uses cstddef:
IntNodePtr search(IntNodePtr head, int target)
{
IntNodePtr here = head;
if (here == NULL) //if empty list
{
return NULL;
}
else
{
while (here->getData( ) != target && here->getLink( ) != NULL)
here = here->getLink( );
if (here->getData( ) == target)
return here;
else
return NULL;
}
}IntNode와 IntNodePtr의 정의는 디스플레이 17.4에 나와 있다.
디스플레이 17.10 이중 연결 리스트
정수의 이중 연결 리스트에 대한 노드 클래스는 다음과 같이 정의할 수 있다:
class DoublyLinkedIntNode
{
public:
DoublyLinkedIntNode ( ) {}
DoublyLinkedIntNode ( int theData, DoublyLinkedIntNode* previous,
DoublyLinkedIntNode* next)
: data(theData), nextLink(next), previousLink(previous) {}
DoublyLinkedIntNode* getNextLink( ) const { return nextLink; }
DoublyLinkedIntNode* getPreviousLink( ) const
{ return previousLink; }
int getData( ) const { return data; }
void setData( int theData) { data = theData; }
void setNextLink(DoublyLinkedIntNode* pointer)
{ nextLink = pointer; }
void setPreviousLink(DoublyLinkedIntNode* pointer)
{ previousLink = pointer; }
private:
int data;
DoublyLinkedIntNode *nextLink;
DoublyLinkedIntNode *previousLink;
};
typedef DoublyLinkedIntNode* DoublyLinkedIntNodePtr;
코드가 단일 연결 리스트의 버전과 거의 동일하다.
바뀐 점
1. private 멤버 변수인 previousLink를 추가했다.
2. previousLink를 초기화하는 생성자에 대한 부가적인 매개변수인
함수 setPreviousLink와 getPreviousLink를 추가했다.
이 함수들을 통해 링크를 가져오고 설정할 수 있다.
3. 이전 노드에 대한 링크 또는 다음 노드에 대한 링크를 구분하기 위해
link라고 불렸던 것도 nextLink로 이름이 변경되었다.
이중 연결 리스트에 노드 추가
리스트 앞에 새로운 DoublyLinkedIntNode를 추가하려면
하나가 아니라 두 개의 노드에 링크를 설정해야 한다.
일반적인 프로세스는 디스플레이 17.11과 같다.
삽입 함수에 대한 선언은 기본적으로 단일 연결된 경우와 같다:
void headInsert(DoublyLinkedIntNodePtr& head, int theData);
1. nextLink가 이전 헤드를 가리키고
previousLink가 NULL인 새 노드를 생성한다.
이 노드는 새 헤드가 되기 때문이다:
DoublyLinkedIntNode* newHead = new DoublyLinkedIntNode
(theData, NULL, head);
2. 기존 헤드는 이전 포인터를 새 헤드에 연결해야 한다:
head->setPreviousLink(newHead);
3. 우리는 head를 새로운 헤드로 설정했다:
head = newHead;
전체 함수 정의는 디스플레이 17.13에 나와 있다.
디스플레이 17.11 이중 연결 리스트의 맨 앞에 노드 추가
새로운 노드를 추가하기 전에 존재하는 리스트
newHead = new DoublyLinkedIntNode(5, NULL, head);
에 의해 생성된 노드
원래 헤드 노드의 이전 링크 설정하기
head를 newHead로 설정하기
이중 연결 리스트에서 노드 삭제
또한 이중 연결 리스트에서 노드를 제거하려면
삭제하고자 하는 노드 양쪽의 참조를 업데이트해야 한다.
역방향 링크 덕분에 단일 연결 리스트에서 했던 것처럼
리스트에서 이전 노드를 계속 추적하기 위한 별도의 변수가 필요하지 않다.
일반적으로 position에 의해 참조되는 노드를 삭제하는 과정은 디스플레이 17.12에 나와 있다.
리스트의 처음이나 끝에서 노드를 삭제하는 것과 같이 일부 특수한 경우는 별도로 처리해야 한다.
디스플레이 17.12 이중 연결 리스트에서 노드 삭제하기
discard 삭제 전 기존 목록
이전 노드와 다음 노드에 포인터 설정
DoublyLinkedIntNodePtr prev = discard->getPreviousLink( );
DoublyLinkedIntNodePtr next = discard->getNextLink( );
discard 우회하기(건너뛰기)
prev->setNextLink(next);
next->setPreviousLink(prev);
discard 삭제
delete discard;
우리의 삭제 함수에 대한 함수 선언은 지금
void delete(DoublyLinkedIntNodePtr& head,
DoublyLinkedIntNodePtr discard);
매개 변수 discard는 제거하고자 하는 노드의 포인터이다.
또한 discard가 head와 같은 경우를 처리하기 위해 head를 입력해야 한다:
if (head == discard)
{
head = head->getNextLink( );
head->setPreviousLink(NULL);
}
이 경우 head를 목록의 다음 노드로 진행시켜야 한다.
그리고 이전 노드가 없으므로 이전 링크를 NULL로 설정한다.
보다 일반적인 경우에는 discard라는 변수가 헤드가 아닌 다른 노드를 가리킨다.
이 경우를 처리하기 위해 discard를 우회하는 링크를 17.12와 같이 재연결한다:
else
{
DoublyLinkedIntNodePtr prev = discard->getPreviousLink( );
DoublyLinkedIntNodePtr next = discard->getNextLink( );
prev->setNextLink(next);
if (next != NULL)
{
next->setPreviousLink(prev);
}
이전 노드는 discard의 다음 노드로 연결되고
다음 노드는 discard의 이전 노드로 연결된다.
discard는 리스트의 마지막 노드일 수 있으므로
함수 setPreviousLink에서 NULL 포인터를 역참조하지 않도록
next!= NULL인지 확인해야 한다.
전체 함수 정의는 디스플레이 17.13에 나와 있다.
디스플레이 17.13 이중 연결 리스트에서 노드 추가 및 제거 함수
노드와 포인터 타입 정의
class DoublyLinkedIntNode
{
public:
DoublyLinkedIntNode ( ) {}
DoublyLinkedIntNode ( int theData, DoublyLinkedIntNode* previous,
DoublyLinkedIntNode* next)
: data(theData), nextLink(next), previousLink(previous) {}
DoublyLinkedIntNode* getNextLink( ) const
{ return nextLink; }
DoublyLinkedIntNode* getPreviousLink( ) const
{ return previousLink; }
int getData( ) const
{ return data; }
void setData( int theData)
{ data = theData; }
void setNextLink(DoublyLinkedIntNode* pointer)
{ nextLink = pointer; }
void setPreviousLink(DoublyLinkedIntNode* pointer)
{ previousLink = pointer; }
private:
int data;
DoublyLinkedIntNode *nextLink;
DoublyLinkedIntNode *previousLink;
}
typedef DoublyLinkedIntNode* DoublyLinkedIntNodePtr;
연결 리스트 맨 앞에 노드를 추가하는 함수
함수 선언
void headInsert(DoublyLinkedIntNode& head, int theData);
//Precondition: The pointer variable head points to
//the head of a linked list .
//Postcondition: A new node containing theData
//has been added at the head of the linked list .
함수 정의
void headInsert(DoublyLinkedIntNodePtr& head, int theData)
{
DoublyLinkedIntNode* newHead = new Doubly LinkedIntNode(theData, NULL, head);
head->setPreviousLink(newHead);
head = newHead;
}
노드를 제거하는 함수
함수 선언
void deleteNode(DoublyLinkedIntNodePtr& head, DoublyLinkedIntNodePtr discard);
//Precondition: The pointer variable head points to
//the head of a linked list and discard points to the node to remove .
//Postcondition: The node pointed to by discard is removed from the list .
함수 정의
FUNCTION DEFINITION
void deleteNode(DoublyLinkedIntNodePtr& head, DoublyLinkedIntNodePtr discard);
{
if (head == discard)
{
head = head->getNextLink( );
head->setPreviousLink(NULL);
}
else
{
DoublyLinkedIntNodePtr prev = discard->getPreviousLink( );
DoublyLinkedIntNodePtr next = discard->getNextLink( );
prev->setNextLink(next);
if (next != NULL)
{
next->setPreviousLink(prev);
}
}
delete discard;
}
예: 연결 리스트 툴의 일반 정렬 템플릿 버전
노드의 T 형식의 데이터로 연결 리스트에서 작동하도록
형식 정의 및 함수 정의를 템플릿으로 변환하는 것은 일상적인 문제이다.
하지만 걱정해야 할 세부 사항이 있다.
중요한 것은
노드에 있는 데이터의 데이터 형식(디스플레이 17.4의 int 형식)을
형식 매개 변수 T로 대체하고
적절한 위치에 다음 사항을 삽입하는 것이다:
template<class T>
그러나 T 형식이 클래스 형식일 수 있다는 사실을 고려하기 위해 몇 가지 사항을 더 수행해야 한다.
T 형식은 클래스 형식일 수 있으므로
T 형식의 값 매개 변수를 상수 참조 매개 변수로 변경하고
T 형식의 반환된 형식은 상수 값으로 반환되도록 const를 추가해야 한다.
(const 값으로 반환하는 이유는 8장에서 설명한다.)
우리가 설명한 변경 사항이 있는 최종 템플릿은 디스플레이 17.14와 17.15에 나와 있다.
정수 형식의 연결 리스트의 단순한 경우에서 한 번 더 변경해야 했다.
템플릿 typedef들은 대부분의 컴파일러에서 구현되지 않기 때문에 사용할 수 없었다.
이것은 때때로 우리가 다음과 같은 읽기 어려운 매개 변수 형식 사양을 사용해야 한다는 것을 의미한다:
Node<T>*&
이것은 Node<T> 형식의 노드에 대한 포인터에 대한 call-by-reference 매개 변수이다.
다음은 Display 17.15에서 함수 선언을 재현하여 상황에 따라 다음 매개 변수 형식 사양을 확인할 수 있다:
template<class T>
void headInsert(Node<T>*& head, const T& theData);
디스플레이 17.14 연결 리스트 라이브러리 인터페이스 파일
//This is the header file listtools.h. This contains type definitions
//and function declarations for manipulating a linked list to store
//data of any type T. The linked list is given as a pointer of type
//Node<T>* that points to the head (first) node of the list. The
//implementation of the functions is given in the file listtools.cpp
#ifndef LISTTOOLS_H
#define LISTTOOLS_H
namespace LinkedListSavitch
{
template<class T>
class Node
{
public:
Node(const T& theData, Node<T>* theLink) : data(theData), link(theLink){}
Node<T>* getLink( ) const { return link; }
const T getData( ) const { return data; }
void setData(const T& theData) { data = theData; }
void setLink(Node<T>* pointer) { link = pointer; }
private:
T data;
Node<T> *link;
};
template<class T>
void headInsert(Node<T>*& head, const T& theData);
//Precondition: The pointer variable head points to
//the head of a linked list .
//Postcondition: A new node containing theData
//has been added at the head of the linked list .
template<class T>
void insert(Node<T>* afterMe, const T& theData);
//Precondition: afterMe points to a node in a linked list .
//Postcondition: A new node containing theData
//has been added after the node pointed to by afterMe .
template<class T>
void deleteNode(Node<T>* before);
//Precondition: The pointer before points to a node that has
//at least one node after it in the linked list .
//Postcondition: The node after the node pointed to by before
//has been removed from the linked list and its storage
//returned to the freestore .
template<class T>
void deleteFirstNode(Node<T>*& head);
//Precondition: The pointer head points to the first
//node in a linked list with at least one node .
//Postcondition: The node pointed to by head has been removed
//from the linked list and its storage returned to the freestore .
template<class T>
Node<T>* search(Node<T>* head, const T& target);
//Precondition: The pointer head points to the head of a linked list .
//The pointer variable in the last node is NULL .
//== is defined for type T .
//(== is used as the criterion for being equal.)
//If the list is empty, then head is NULL .
//Returns a pointer that points to the first node that
//is equal to the target. If no node equals the target,
//then the function returns NULL .
}//LinkedListSavitch
#endif //LISTTOOLS_H기존에 const T&을 사용했던 매개변수 형식으로 T를 사용해도 무방할 것 같다.
T가 클래스 형식이 될 것으로 예상되어 상수 참조 매개변수를 사용했다.
디스플레이 17.15 연결 리스트 라이브러리 구현 파일
//This is the implementation file listtools.cpp. This file contains
//function definitions for the functions declared in listtools.h.
#include <cstddef>
#include "listtools.h"
namespace LinkedListSavitch
{
template<class T>
void headInsert(Node<T>*& head, const T& theData)
{
head = new Node<T>(theData, head);
}
template<class T>
void insert(Node<T>* afterMe, const T& theData)
{
afterMe->setLink(new Node<T>(theData, afterMe->getLink( )));
}
template<class T>
void deleteNode(Node<T>* before)
{
Node<T> *discard;
discard = before->getLink( );
before->setLink(discard->getLink( ));
delete discard;
}
template<class T>
void deleteFirstNode(Node<T>*& head)
{
Node<T> *discard;
discard = head;
head = head->getLink( );
delete discard;
}
//Uses cstddef:
template<class T>
Node<T>* search(Node<T>* head, const T& target)
{
Node<T>* here = head;
if (here == NULL) //if empty list
{
return NULL;
}
else
{
while (here->getData( ) != target && here->getLink( ) != NULL)
here = here->getLink( );
if (here->getData( ) == target)
return here;
else
return NULL;
}
}
} //LinkedListSavitch
'프로그래밍 공부 > OOP' 카테고리의 다른 글
| 17장 연계된 자료 구조(3) (0) | 2023.12.01 |
|---|---|
| 17장 연계된 자료 구조(2) (2) | 2023.12.01 |
| 16장 탬플릿 (1) | 2023.11.30 |
| 15장 다형성과 가상함수 (1) | 2023.11.30 |
| 14장 상속 (0) | 2023.11.29 |