오늘은 연결리스트에 대해 정리해보았다. 그럼 따라와보자
1. 리스트의 개념
원소들 간의 순서가 지켜지며 유지되는 자료구조
리스트의 순서는 데이터가 저장되는 물리적인 위치와 상관없이
사람들의 머릿속에 인식되는 논리적인 순서, 혹은 원소들 간의 의미적인 순서이다
배열은 순서와 관련된 자료구조이다
배열은 인덱스로 표현되는 순서가 === 메모리(주기억장치, DDR) 내의 물리적인 저장순서를 결정한다
리스트 구현 방법
1. 리스트는 배열을 이용하여 구현한다
2. 리스트는 원소 값을 저장하는 공간 + 다음 원소의 위치 정보를 저장하는 공간으로 구현한다
2. 배열을 이용한 리스트의 구현
👍 리스트의 원소값을 순서대로 배열에 저장 (간 - 단)
👍 메모리의 공간 활용 효율이 높다 ↑ (포인터를 위한 메모리가 필요X)
👎 하지만 삽입과 삭제에 많은 시간이 든다 (특히 중간에 삽입하려면 원소들을 뒤로 한칸씩 밀어야 한다 / 프로그램 수행시간↑)
→ 배열은 비효율적이라 포인터를 이용하게 되었다
3. 포인터를 이용한 리스트의 구현
포인터를 이용하여 구현되는 리스트를 연결 리스트 라고 한다
리스트는 노드 간의 포인터 연결을 통해 구현되며 각 노드는 적어도 두 종류의 필드 데이터 필드 + 링크 필드를 가진다
노드는 리스트의 원소값(데이터) + 다음 원소를 지시하는 포인터(a.k.a 링크)로 구성된다
노드는 리스트의 원소값(데이터) + 다음 원소의 메모리 주소로 구성된다
(모두 같은 말이다)
이 주소 값을 이용해서 리스트의 다음 원소를 찾는다
포인터 변수 HEAD는 시작 노드를 가리킨다
마지막 노드의 링크는 null pointer 이다
나머지 노드들의 링크는 논리적으로 다음에 위치하는 노드를 가리키는 주소를 가지게 된다
4. 포인터 변수
포인터 변수는 주소 값을 담고있다
포인터 변수는 char, int, float, double, struct 등 데이터 타입을 지정한다 (변수에 주소값을 저장하기 위해)
int a = 100; // 변수 a에 100을 저장 → 100을 메모리에 이사시키면서 주소가 생긴다
int *b ; // *b 는 주소 전용 변수라고 보면 된다 (할당전이라 빈칸)
b = &a; // b에 &a(a의 메모리 주소)를 담는다 (할당 완 - 료)
1. 정수형 변수 a가 선언되면서 동시에 정수값 100이 할당된다. 또 FF00 주소에 100이 저장된다
→ 메모리의 일정 영역을 할당 받는다 / a의 이름으로 메모리 주소가 부여된다
2. 정수형 포인터 변수 b를 선언하며 FF01 주소만 할당받는다 (값은 비어있음)
→ *을 붙여서 b는 포인터 전용이 되었다
3. &a 는 a 의 메모리주소인 FF00 을 반환한다. 그걸 b에 할당해준다
→ b는 포인터 전용이라 FF00(a의 주소)은 b의 메모리 영역에 값으로 저장 이 된다
** & 역참조 연산자
&는 단항연산자이고 역참조 연산자이다
&a 는 변수 a의 메모리 주소를 결과값으로 돌려 준다
int a = 100;
int *b ;
b = &a;
printf("a is %d \n", a); // 100
printf("*b is %d \n", *b); // 100
*b 는 a의 주소를 추출하고 FF00을 찾아간다 → FF00 에 저장된 값인 100 을 반환
여기서 b는 a의 주소값 그 자체이고 *b는 역참조해서 그 주소에서 꺼내온 데이터값 이다
int a;
int *b; // 포인터변수 ㅅ
b = &a; // b에 &a 주소값을 할당
a = 100;
*b = 200; // b가 들고있는 주소의 값을 200으로 저장, a = 200 으로 동일
*b 는 b가 저장되어 있는 주소값이 가리키는 메모리영역을 찾아가고, 200을 저장한다
실제로 a에 200 을 저장하는 것과 같다
구조체 포인터 타입
c 언어에서는 struct 라는 구조체를 객체 대신 사용한다. 노드도 마찬가지이다
// 구조체 포인터 선언
struct linked_list_node {
int data; // 데이터 값
struct linked_list_node *link; // 포인터 구조체
}
구조체 동적 메모리 할당
- malloc 함수
프로그램 실행중 메모리 공간을 할당 받을 수 있다.
프로그래머기 요구한 크기의 메모리 영역에 대한 주소값을 반환해주면 이 주소값을 포인터 변수로 받아 저장하여 사용하게 된다
- sizeof(int)함수
정수형 데이터 메모리 공간 크기를 반환한다
malloc(sizeof(int)) 는 정수형 데이터를 저장할 수 있는 크기의 메모리 공간을 할당하여 주소값을 반환한다
-free 함수
malloc 함수를 이용하여 할당받은 메모리 공간을 없애고 다른 프로그램에서 사용할 수 있도록 해준다
**포인터를 사용하여 프로그램을 작성하면 프로그램의 융통성과 효율성을 높일 수 있지만, 프로그램이 멈추거나 오작동을 초래할수도..
int a, *p_a; // 변수와 포인터변수 선 - 언
float b, *p_b; // 변수와 포인터변수 선 - 언
p_a = (int *)malloc(sizeof(int)); // 정수형 데이터 메모리 주소값
p_b = (float *)malloc(sizeof(float)); // 실수형 데이터 메모리 주소값
*p_a = 10; // 데이터 저장
*p_b = 3.14; // 데이터 저장
// 반환값
// a = 10
// b = 3.14
// *p_a = 10
// *p_b = 3.14
free(p_a) // 메모리 할당 해제
free(p_b) // 메모리 할당 해제
5. 연결리스트의 여러가지 연산 프로그램
- 연결 리스트의 생성
별거없다. 헤드 노드만 생성하면 된다
typedef struct ListNode { // 리스트 노드 정의 (data + link)
int data[10]; // 10개의 숫자 데이터의 공간을 할당
struct ListNode* link; // 포인터 변수 정의 (구조체가 ListNode타입)
} listNode; // 자료형은 ListNode 전체를 가리키는 포인터 변수이다
typedef struct { // 헤드 노드 구조 정의
listNode* head; // 헤드용 포인터 변수 정의
} linkedList_h;
linkedList_h* createLinkedList_h(void) { // 연결 리스트 생성
linkedList_h* H; // 헤드노드 H 정의
H = (linkedList_h*)malloc(sizeof((linkedList_h)); // H의 공간먼저 할당받고
H → head = NULL; // H값은 NULL 로 비워두자
return H; // H만 리턴
}
- 연결 리스트의 노드 삽입
맨 마지막에 노드를 삽입하고자 한다
void addNode(linkedList_h* H, int x){
// 노드 준비
listNode* NewNode; // 새로 추가할 노드랑
listNode* LastNode; // 마지막 노드를 정의!
// NewNode 셋업
NewNode = (listNode*)malloc(sizeof(listNode)); // 메모리 할당해주고
NewNode → data = x; // 새로 추가할 노드의 데이터에 x 를 넣어준다
NewNode → link = NULL; // 새로 추가할 노드의 링크에 null 를 넣어준다
// 신규 리스트인 경우
if(H → head == NULL){ // 헤드값이 비었으면
H → head = NewNode; // 새로 추가할 노드를 헤드로 만들고
return; // 퇴장
}
// LastNode 셋업
LastNode = H → head; // H -> head의 주소값을 LastNode 에 저장
// 마지막 노드 찾기
while(LastNode → link != NULL){ // link가 null이 아니면 (=마지막 노드가 아니면)
LastNode = LastNode → link; // LastNode는 LastNode의 link가 가리키는 값이 된다
}
// 마지막 노드를 찾은 후
LastNode → link = NewNode; // 마지막 노드의 링크에 NewNode 를 연결시켜준다
}
- 연결 리스트의 노드 삭제
맨 마지막의 노드를 삭제하고자 한다
void deleteNode(linkedList_h* H){ // 매개변수로 헤드가 필요
// 준비물 선언
listNode* prevNode; // 이전 노드와
listNode* delNode; // 삭제할 노드를 정의!
// 신규 리스트일 때
if(H → head == NULL) return; // 가차없이 종 - 료
// 리스트에 헤드 하나인 경우
if(H → head → link == NULL){
free(H → head); // head 를 free 시켜주고
H → head = NULL; // head 를 NULL 로 만들어주고
return; // 탈 - 퇴
// 리스트에 값이 차있는 경우 (본론 로직)
} else {
// 초기값 설정
prevNode = H → head; // 이전노드를 헤드(그 잡채)로
delNode = H → head → link; // 삭제할 노드를 헤드의 다음 순서로
// 삭제할 노드의 다음 값이 있는 경우
while(delNode → link != NULL){
prevNode = delNode; // 이전 노드를 = 삭제할 노드의 값으로 대체
delNode = delNode → link; // 삭제할 노드는 = 그 다음 순서인 노드로 교체
}
// 마지막 노드까지 도달한 경우
free(delNode); // delNode의 메모리를 free 시키고
prevNode → link = NULL; // 이전 노드의 다음값을 비운다
}
}
- 연결 리스트의 특정 노드 삭제
헤드 노드와 삭제하고자 하는 노드 앞의 노드를 가리키는 선행 노드와 삭제하고자 하는 노드의 값을 매개변수로 전달받는다.
바로 delNode 를 삭제하면 del의 다음 노드를 모르게 된다. 그래서 삭제 전에 prevNode 의 링크 값을 === delNode 의 다음 주소값으로 변경해주어야 한다
// 매개변수로 헤드, 삭제할 노드의 이전 순서 노드, 삭제할 노드가 필요
void deleteItNode(linkedList_h* H, listNode* prevNode, listNode* delNode){
prevNode → link = delNode → link; // 이전 노드의 링크를 삭제할 노드의 다음 노드로 교체한다
free(delNode); // 삭제할 노드를 영원히 byebye
return;
}
- 연결 리스트의 특정 노드 삽입
// 매개 변수로 헤드 노드(H)와 이전 노드(prevNode), 삽입할 데이터(itdata)를 받는다
void addItNode(linkedList_h* H, listNode* prevNode, int itdata){
// 함수 내부에서 사용할 NewNode 선언
listNode* NewNode;
// 리스트 노드에 대한 메모리 할당
NewNode = (listNode*)malloc(sizeof(listNode));
// 삽입할 노드 data, link 세팅
NewNode → data = data;
NewNode → link = NULL;
// 삽입할 노드의 링크는 = 이전 노드의 링크로 교체
NewNode → link = prevNode → link;
// 이전 노드의 링크는 새로 삽입할 노드로 향한다
prevNode → link = NewNode;
}
- 연결 리스트의 특정 노드 검색
void searchNode(linkedList_h* H, int itdata){ // 헤드와 검색할 값을 매개변수로 넣고
// 임시변수 세팅
listNode* tempNode; // 임시 변수를 선언하고
tempNode = H → head; // 헤드로 값을 저장한다
// 임시변수의 데이터가 검색한 값이 아니면
while(tempNode → data != itdata){
tempNode = tempNode → link; // 임시변수를 그 다음 값으로 자체 변경한다
}
// 검색한 값을 찾고 난 뒤
printf("search ok \n"); // 검색이 성공했음을 만천하에 알린다
}
'OS & Network' 카테고리의 다른 글
| 자료구조 - 트리란 (1) | 2023.12.03 |
|---|---|
| 자료구조 - 연결리스트의 응용 (3) | 2023.12.01 |
| 자료구조 - Array(배열)이란 (1) | 2023.11.26 |
| 자료구조 - Queue(큐)란 (1) | 2023.11.24 |
| 자료구조 - Stack이란 (3) | 2023.11.23 |
댓글