배열
- 데이터를 순차적으로 입력시키며, 물리적 주소 또한 순차적이다.
- 배열의 크기는 처음에 결정되고, 변경이 불가능하다.
- 크기가 고정적이고 인덱스를 가지고 있어, 검색속도가 빠르다.
- 삽입/삭제 작업이 번거롭다.(배열 중간에 삽입할 경우, 모든 값을 이동시켜야 하고 배열이 꽉 찼을 경우, 메모리 재 할당이 필요함)
연결 리스트
- 원소들 간의 논리적 순서를 위한 자료구조
- 원소들 간의 순서는 논리적으로 지켜지며, 물리적 위치는 상관하지 않는다.
- 메모리 할당/해제를 통해 유연한 크기변경이 가능하다.
- 할당된 인덱스는 없으며, 위치를 기억하고 있다.
- 특정 데이터에 접근하기 위해 연결된 위치들을 따라서 접근해야 하기 때문에 검색 속도가 느리다.
- 삽입, 삭제 시 리스트의 위치만 변경하기 때문에 속도가 빠르다.
- 일반적으로 포인터 변수를 이용하여 연결 리스트를 구성한다.
<리스트 예시>
단순 연결 리스트 구현
연결 리스트 생성
typedef struct listNode { // Node 구조 정의
int data[10]; // 데이터 공간
struct listNode* link; // 다음 노드를 가리키기 위한 변수
} listNode;
typedef struct { // 헤드노드 구조 정의(첫 번째 노드를 가리키는 역할)
listNode* head;
} headNode;
headNode createLinkedList(void) { // 연결 리스트 생성(헤드노드 하나를 생성하여 반환)
headNode* H;
H = (headNode*)malloc(sizeof(headNode*));
H -> head = NULL;
return head;
}리스트의 마지막에 노드 추가
void addNode(headNode* H, int x) { // 노드 추가
listNode* newNode;
listNode* lastNode;
newNode = (listNode*)malloc(sizeof(listNode));
newNode -> data = x;
newNode -> link = NULL;
if(H -> head == NULL) { // 현재 리스트가 공백인 경우
H -> head = newNode; // H가 가리키는 헤드노드가 추가된 노드를 가리킨다.
return;
}
lastNode = H -> head;
while(lastNode -> link != NULL) lastNode = lastNode -> link; // 마지막 노드 찾기
lastNode -> link = newNode; // 마지막 노드에 추가된 노드 연결
}
리스트의 마지막 노드 삭제
void deleteNode(headNode* H) { // 마지막 노드 삭제 연산
listNode* prevNode;
listNode* delNode;
if(H -> head == NULL) return; // 빈 리스트인 경우 삭제할 노드가 없으므로 종료
if(H -> head -> link == NULL) { // 리스트에 노드가 한 개인 경우
free(H -> head); // 메모리 해제 후 리턴
H -> head = NULL;
return;
}
else { //리스트에 노드가 2개 이상인 경우
prevNode = H -> head;
delNode = H -> head -> link;
while(delNode -> link != NULL) {
prevNode = delNode;
delNode = delNode -> link;
}
free(delNode);
prevNode -> link = NULL;
}
}특정 노드 뒤에 삽입
// 삽입할 선행 노드(prevNode)에 대한 포인터를 매개변수로 받아서 처리
void addItNode(headNode* H, listNode* prevNode, int x) {
listNode* newNode;
newNode = (listNode*)malloc(sizeof(listNode));
newNode -> data = x;
newNode -> link = NULL;
newNode -> link = prevNode -> link;
prevNode -> link = newNode;
return;
}특정 노드 삭제
// 삭제할 노드(delNode)와 선행 노드(prevNode)를 받아서 처리
void deleteItNode(headNode* H, listNode* prevNode, listNode* delNode) {
prevNode -> link = delNode -> link;
free(delNode);
return;
}특정 노드 검색
void searchNode(headNode* H, int x) { //데이터 필드 값이 x인 노드 검색
listNode* tempNode;
tempNode = H -> head;
while(tempNode -> data != x) {
tempNode = tempNode -> link;
}
printf("Search Successful.\n");
}
참고
Security & Develop