이중 연결 리스트(Doubly Linked List) 구현

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

81

82

83

84

85

86

87

88

89

90

91

92

93

94

95

96

97

98

99

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

#include <iostream>

using namespace std;

 

class Node

{

public:

    int key;

    Node* llink;

    Node* rlink;

};

void print(Node* st) {

    Node* curr = st;

    while (true) {

        printf("%d 번 ", curr->key);

        if (curr->rlink == NULL) {

            break;

        }

        else {

            curr = curr->rlink;

        }

    }

}

 

Node* create(int key) {

    printf("%d로 시작 노드 생성.\nresult : ",key);

    Node* start = new Node();

    start->key = key;

    start->rlink = NULL;

    print(start);

    printf("\n");

    return start;

}

 

 

void insert(Node* st, int key) {

    printf("%d를 삽입합니다.\n", key);

    Node* cur = new Node();

    Node* now = st;

    cur->key = key;

    if (st->rlink == NULL or st->key == cur->key) {

        st->rlink = cur;

        cur->llink = st;

    }

 

    else {

        while (now->rlink != NULL)

        {

            if (cur->key > now->key && cur->key < now->rlink->key) {

                cur->rlink = now->rlink;

                cur->llink = now;

                now->rlink->llink = cur;

                now->rlink = cur;

                break;

            }

 

            now = now->rlink;

        }

        if (now->rlink == NULL) {

            now->rlink = cur;

            cur->llink = now;

        }

    }

    printf("result : ");

    print(st);

    printf("\n");

}

 

void dlt(Node* st, int key) {

    Node* now = st;

    int n = 1;

    do {

        if (now->key == key) {

            printf("제거할 요소 (%d)를 찾았습니다. %d번째에 위치합니다.\n", key, n);

            now->llink->rlink = now->rlink;

            now->rlink->llink = now->llink;

            free(now);

            printf("result : ");

            print(st);

            printf("\n");

            return;

        }

        now = now->rlink;

        n++;

    } while (now->rlink != NULL);

    if (now->rlink == NULL && key == now->key) {

        printf("제거할 요소 (%d)를 찾았습니다. 마지막에 위치합니다.\n",key);

        now->llink->rlink = now->rlink;

        free(now);

        printf("result : ");

        print(st);

        printf("\n");

        return;

    }

    printf("제거할 요소 (%d)를 찾지 못했습니다.\n", key);

}

 

int main() {

    Node* st = create(1);

    insert(st, 4);

    insert(st, 3);

    insert(st, 2);

    insert(st, 5);

    dlt(st, 2);

    dlt(st, 5);

    dlt(st, 8);

 

    print(st);

}