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

-배열로 구현

장점

 

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

*구현이 간단하다

 

단점

 

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

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

 

[배열로 구현]

 

?

1 2 3 4 5 6 7 8 9

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)

?

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80

#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