[자료구조] 연결리스트(Linked List) 배열로 구현하기

-배열로 구현

장점

 

*특정 위치에 있는 값을 찾는 시간이 빠르다.

*구현이 간단하다

 

단점

 

*삽입/ 삭제 시 오버헤드 (O(n))

*노드의 개수가 정적크기이다. (처음에 정해지고 변하지 않는다.)

 

[배열로 구현]

 

void addFirst(struct List *target, int data) void add (struct List *target, int data, int pos) :특정 위치에 값 삽입 void addLast(struct List *target, int data) void deleteEle(struct List *target, int pos) : 특정 위치의 값 삭제 void allClear(struct List *target) : 리스트 모두 초기화 int findValue(struct List *target, int data) : 특정 위치 값 찾기 void replace(struct List *target, int pos, int value) : 특정 위치의 값 변경 int isFull(struct List *target) int isEmpty(struct List *target) #include <stdio.h> #include <stdlib.h> #define MAXX 5001 struct List{ int array[MAXX]; int length = 0; }; void addFirst(struct List *target, int data) { if (target->length == MAXX) return; else { target->array[target->length++] = data; } } void add (struct List *target, int data, int pos) { if (target->length == MAXX) return; else if (target->length < pos){ addFirst(target, data); } else { for (int i = target->length; i> pos; i--) { target->array[i] = target->array[i-1]; } target->array[pos] = data; target->length++; } } void addLast(struct List *target, int data) { if (target->length == MAXX) return; target->array[target->length++] = data; } void deleteEle(struct List *target, int pos) { if (target->length == 0) return; if (pos > target->length) return; for (int i = pos-1; i< target->length-1; i++) { target->array[i] = target->array[i+1]; } target->length--; } void allClear(struct List *target) { target->length = 0; } int findValue(struct List *target, int data) { for (int i = 0; i < target->length; i++) { if (target->array[i] == data) return i; } } void replace(struct List *target, int pos, int value) { target->array[pos-1] = value; } int isFull(struct List *target) { if (target->length == MAXX) return 1; return 0; } int isEmpty(struct List *target) { if (target->length == 0) return 1; return 0; } int main() { struct List *head = (struct List*)malloc(sizeof(struct List)); int n, k; scanf("%d %d", &n, &k); for (int i = 1; i <= n; ++i) { add(head, i , i-1); } for (int i = 0; i < head->length; i++) { printf("%d", head->array[i]); } free(head); }

 

n= 7

 

head-> array

1

2

3

4

5

6

7