리스트의 개념
리스트의 의미
- 일정한 순서 의 나열
- 어떤 정의에 의해 결정된 논리적인 순서 의 나열
배열의 정의
- 원소의 메모리 공간(메인 메모리, DDR) 의 물리적인 위치를 순서 적으로 결정하는 특징
- 배열의 순서는 메모리 공간에서 저장되는 원소값의 물리적 순서
→ 리스트의 순서는 데이터가 저장되는 물리적인 위치와 상관없이 사람들의 머릿속에 인식되는 논리적인 순서 혹은 리스트에 나타나는 원소들 간의 의미적인 순서를 의미함
리스트의 구현 방법
- 포인터를 이용한 리스트의 구현 방법
→ 원소 값을 저장하는 공간과 다음 원소를 가리키는 위치 정보를 저장하는 공간을 함께 구현하는 방법
- 배열을 이용한 리스트의 구현 방법
배열을 이용한 리스트의 구현
배열을 이용한 리스트의 구현
- 구현해야 할 리스트가 3.1 운동(1919) ,8.15 광복(1945) , 6.25 전쟁(1950) , 서울올림픽(1988) 의 순서라고 정의 하면
리스트 : (1919,1945,1950,1988)
배열을 이용한 리스트의 원소 삽입
→ 해당 리스트에 애국가 작곡(1936)을 삽입한다면
리스트 : (1919, 1936,1945,1950,1988) 이 되야 함. 중간에 하나의 추가로 한칸씩 밀리는 값들이 생김.
배열의 확장
초기 배열 선언에서 충분히 크게 하면 어느정도는 배열의 추가 확장을 피할 수 있겠지만(메모리낭비), 원소를 리스트의 중간에 삽입하기 위해서는 리스트의 원소 값을 하나씩 뒤로 밀어야 하는 상황 발생. (연산 시간 증가)
배열을 이용한 리스트의 원소 삭제
→ 해당 리스트에 애국가 작곡(1936)을 삭제하면,
리스트 : (1919, 1945,1950,1988) 잡혀 있던 공간의 빈공간이 발생
배열을 이용한 리스트의 원소 삽입/삭제
- 배열로 구현된 리스트 는 원소의 순서가 연속적인 물리적 주소에 저장됨
→ 원소를 삽입하거나 삭제하기 위해서는 해당 원소의 위치 뒤에 있는 모든 원소를 뒤로 물리거나 앞으로 당겨야 한다.
→ 리스트 원소 값이 이동은 원소수가 많을수록 프로그램의 수행 시간을 증가시킴
배열을 이용한 리스트의 원소 삽입/삭제 시 발생하는 문제
- 리스트의 원소 삽입은 프로그램의 실행중에 메모리 할당을 필요로 하는 경우도 발생시킴
- 배열을 이용한 리스트의 구현은 실제 IT 서비스 환경에서는 자주 사용되지 않고 있음
- 자료의 삽입과 삭제가 빈번히 발생하는 상황에서 리스트를 배열로 구현하는 것은 빈번한 자료 이동으로 인한 비효율적인 컴퓨팅 성능 유발
포인터를 이용한 리스트의 구현
노드의 구조
- 노드(node) : 리스트 의 원소값(데이터) + 다음 원소를 가리키는 정보(포인터)
- 노드는 데이터 요소( 원소값) 과 리스트의 다음 노드를 지시하는 포인터(주소,링크(link)) 로 구성됨
포인터 변수
리스트의 생성
- 정수 값 data 와 링크 link 로 구성 된 노드의 생성
struct lunked_list_node{
int data;
lunked_list_node * link;
}
포인터의 할당 과 반환의 예시
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;
printf('a is %d', "b is %f\\n", *p_a, *p_b);
free(p_a);
frre(p_b);
포인터 의 할당과 반환의 실행 결과
p_a = (int *)malloc(sizeof(int));
p_b = (float *)malloc(sizeof(float));
연결 리스트의 삽입과 삭제
연결리스트에서 노드의 삭제
- 리스트의 원소 삭제 연산 단계
→ 식제할 노드의 선행 노드의 링크 필드를 삭제 할 노드의 후행 노드를 가리키게 한다.
→ 삭제할 노드를 메모리에 반환한다.
- 리스트의 원소 삽입 연산 단계
→ 메모리 공간을 할당받고 삽입 할 내용을 저장하여 삽입할 x노드를 생성합니다.
→ x노드의 링크부분이 후행 노드가 될 j 노드를 가리키게 합니다.
→ 삽입될 x 노드의 선행 노드가 될 i 노드의 링크 필드가 x 노드를 가리키게 합니다.
연결리스트의 여러가지 연산 프로그램
연결리스트의 생성
typedef struct ListNode { // 단순 연결 리스트의 노드 구조 정의
int data;
struct ListNode * link;
} listNode;
typedef struct { // 리스트의 헤드 (first) 노드 구조 정의
listNode * head;
}linkdedList_h;
linkdedList_h* createLinkedList_h(void) { //연결리스트 생성
linkedList_h* H;
H = (linkedLit_h *) malloc(sizeof(linkedList_h));
H -> head = Null;
return H;
}
연결리스트의 노드 삽입
void addNode(linkedList_h* H , int x) {
// 리스트 마지막 노드에 삽입 연산하며, x 값은 100 이라고 가정함
listNode * New Node ;
listNode * LastNode;
NewNode = (listNode*)malloc(sizeof(listNode));
NewNode -> data = x;
NewNode -> link = Null;
}
// newNode
// data | x
// link | null
if(H -> head == null) { // 현재 리스트가 공백인 경우
H -> head = NewNode;
return;
}
LastNode = H -> head;
while(LastNode -> link != Null) LastNode = LastNode -> link;
LastNode -> link = Newnode;
}
- 연결리스트의 헤드에 노드 삽입 (빈 연결리스트의 경우)
→ NewNode 생성
- 연결 리스트 위에 한개의 노드 삽입
→ 마지막 노드 뒤에 NewNode 생성
연결 리스트의 특정 노드 뒤에 새 노드의 삽입 연산
void addItNode(linkedList_h* H, listNode*, prevNode, int itdata ){
// 리스트 중간에 노드를 삽입하는 연산하며, itdata 값은 150 이라고 가정함
listNode* NewNode;
NewNode = (listNode*)malloc(sizeof(listNode));
NewNode = data = itdata;
NewNode = link = NULL;
NewNode = link = prevNode -> link;
prevNode = link = NewNode;
return ;
}
// newNode
// data 150
// link NULL
- prevNode 가 NewNode 를 가리키면 안된다. (실패)
→ newNode 의 link 가 연결이 안되어 있기 때문에 다음을 추론 할 수 없다.
- newNode의 링크 필드 값이 먼저 변경 되야 한다.
NewNode -> link = prevNode -> link;
prevNode -> link = NewNode;
연결리스트의 마지막 노드 삭제
void deleteNode(linkedList_h* H){ // 리스트의 마지막 노드 삭제
listNode* prevNode;
listNode* delNode;
if(H -> head == NULL) return ; // 공백 리스트인 경우, 삭제 연산 중단
if(H -> head -> link == NULL) { // 리스트에 노드가 한 개 인 경우
free(H -> head); // 첫 번째 노드의 메모리를 해제
H -> head = NULL;
return;
}
}
else { // 리스트에 노드가 여러개 있는 경우
prevNode = H -> head;
delNode = H -> head -> link;
while(delNode -> link != NULL) {
prevNode = delNode;
delNode = delNode -> link;
}
free(delNode);
prevNode -> link = NULL;
}}
- 리스트의 노드가 한개 인 경우
→ h 의 값을 null 로 바꾸면 됨
- 연결 리스트의 노드가 여러개인 경우
→ delNode 를 삭제 시키고 prevNode 의 link 값을 null 처리
연결 리스트의 특정 노드 검색
void fineandDeleteNode(linkedList_h* H, int itdata) {
// 연결 리스트에서 특정 노드를 검색하여 삭제하고자 하는 연산, itdata = 200
listNode* prevNode;
listNode* delNode;
if(H -> gead == NULL) return; // 공백 리스트
prevNode = H;
delNode = H -> head;
}
while(delNode != NULL) {
if(delNode -> data == itdata){
deleteitNode(H,prevNode,delNode);
return;
}
else {
prevNode = delNode;
delNode = delNode -> link;
}
}
- 변경된 delNode 의 위치 값
→ head 부터 data 의 값을 비교 해서 일치 하지 않으면 다음으로 넘어감
연결 리스트의 특정 노드의 삭제
void deleteItNode(linkedList_h* H, listNode* preveNode, listNode* delNode){
// 연결 리스트에서 데이터의 값이 200인 노드(delNode) 를 삭제 연산
prevNode -> link = delNode -> link;
free(delNode);
return;
}
댓글