연결리스트 클래스

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
#파일 이름: sllist.py

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None


class Linked_list:
    def __init__(self):
        self.head = None
        self.length = 0

    def __len__(self):
        return self.length

    def __str__(self):
        if self.head is None:
            return "Empty List"
        node = self.head
        string = ""
        while node.next:
            string += str(node.data) + " → "
            node = node.next
        return string + str(node.data)

    def __contains__(self, data):
        node = self.head
        while node:
            if node.data == data:
                return True
            node = node.next
        return False

    def appendleft(self, data):
        node = Node(data)
        if self.head is None:
            self.head = node
        else:
            node.next = self.head
            self.head = node
        self.length += 1

    def append(self, data):
        node = Node(data)
        if self.head is None:
            self.head = node
        else:
            prev = self.head
            while prev.next:
                prev = prev.next
            prev.next = node
        self.length += 1

    def popleft(self):
        if self.head is None:
            return None
        node = self.head
        self.head = self.head.next
        self.length -= 1
        return node.data

    def pop(self):
        if self.head is None:
            return None
        node = self.head
        if self.head.next is None:
            self.head = None
        else:
            while node.next is not None:
                prev = node
                node = node.next
            prev.next = None
        self.length -= 1
        return node.data

    def insert(self, i, data):
        if i <= 0:
            self.appendleft(data)
        elif i >= self.length:
            self.append(data)
        else:
            prev = self.head
            for _ in range(i - 1):
                prev = prev.next
            node = Node(data)
            node.next = prev.next
            prev.next = node
            self.length += 1

    def remove(self, data):
        if self.head.data == data:
            self.popleft()
            return True
        prev = self.head
        while prev.next:
            if prev.next.data == data:
                prev.next = prev.next.next
                self.length -= 1
                return True
            prev = prev.next
        return False

    def reverse(self):
        if self.length <= 1:
            return
        ahead = self.head.next
        prev = self.head
        prev.next = None
        while ahead:
            self.head = ahead
            ahead = ahead.next
            self.head.next = prev
            prev = self.head

연결리스트 테스트

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
def get_data(msg):
    print(msg, end = ">>> ")
    data = input()
    return int(data) if data.isdigit() else data

my_list = LinkedList()

while True:
    menu = """
-----------------------
실행할 명령어를 선택하세요.

[0] 연결 리스트의 상태 출력
[1] 처음에 노드 추가   [2] 끝에 노드 추가      [3] 노드 검색
[4] 첫 노드 꺼내기     [5] 마지막 노드 꺼내기  [6] 특정 위치에 노드 삽입
[7] 노드 삭제         [8] 연결 리스트 뒤집기
[9] 끝내기

"""
    print(menu, end=" >>> ")
    command = int(input())
    print("-----------------------")
    print()

    if command == 0:
        print(my_list)
    elif command == 1:
        my_list.appendLeft(get_data("추가할 값(정수, 문자)을 입력하세요."))
    elif command == 2:
        my_list.append(get_data("추가할 값(정수, 문자)을 입력하세요."))
    elif command == 3:
        data = get_data("검색할 값을 입력하세요.")
        if data in my_list:
            print(f"{data}(이)가 리스트에 있습니다.")
        else:
            print(f"{data}(이)가 리스트에 없습니다.")
    elif command == 4:
        print(my_list.popLeft())
    elif command == 5:
        print(my_list.pop())
    elif command == 6:
        index = get_data("값을 추가할 인덱스를 입력하세요.")
        my_list.insert(index, get_data("추가할 값을 입력하세요."))
    elif command == 7:
        data = get_data("삭제할 값을 입력하세요.")
        if my_list.remove(data):
            print(f"{data}(을)를 정상적으로 삭제했습니다.")
        else:
            print(f"{data}(이)가 리스트에 없습니다.")
    elif command == 8:
        my_list.reverse()
        print("리스트를 뒤집었습니다.")
    elif command == 9:
        break