[자료구조]2. 링크드 리스트 - 4 정리 + 메인 프로그램 만들기

 저번 포스팅까지해서 링크드 리스트가 모두 정리됐습니다!

이번 글에서는 링크드 리스트에 대한 정리와 링크드 리스트 활용을 해보기 위한 메인 프로그램 만들기를 해보겠습니다.

 

 

---

<링크드 리스트 글 모음>

2. 링크드 리스트 - 1 싱글 링크드 리스트

[자료구조] 2. 링크드 리스트 - 1 싱글 링크드 리스트

2. 링크드 리스트 - 2 더블 링크드 리스트

[자료구조] 2. 링크드 리스트 - 2 더블 링크드 리스트

 

2. 링크드 리스트 - 3 환형 링크드 리스트

[자료구조]2. 링크드 리스트 - 3 환형 링크드 리스트

 

링크드 리스트에 대한 정리

 링크드 리스트의 목적은 사이즈의 제한 없이 유연하게 크기를 바꿀 수 있게 하는데 있습니다. 그래서 스택, 큐, 트리와 같은 자료구조의 기반이 되기도 합니다.

가장 중요한 부분

• 노드 : 개인적으로 노드라는 리스트의 요소 형태를 이해하는 것이 가장 중요하다고 생각합니다. 데이터 파트와 다른 노드를 가리키는 포인터에 대해서 생각하고 설계하는 게 중요합니다.
• 리스트 별 차이점을 이해하면 어디에 필요한 지 알기 쉬울 것입니다.

	싱글 링크드 리스트	더블 링크드 리스트	환형 링크드 리스트
구조	헤드에서 테일로 일방향으로 연결됨	양방향으로 연결됨	양방향으로 연결되어 있고 헤드와 테일이 연결됨
노드 포인터 개수	1개(next)	2개(prev, next)	2개(prev, next)
헤드 이전	X	X	O (테일과 연결)
테일 이후	X	X	O (헤드와 연결)
구현 난이도	가장 쉬움	복잡함	복잡함
탐색 방법	헤드에서 차례대로 탐색	테일과 헤드 양쪽에서 탐색 가능	테일과 헤드 양쪽에서 탐색 가능
테일 탐색 방법	헤드에서 맨 마지막 노드까지 가야함	헤드에서 맨 마지막 노드까지 가야함	헤드의 이전 노드를 선택함

물론 파이썬에는 기본적으로 리스트 구조가 클래스로 구현되어 있습니다. 그래도 한번씩 구현해보면 리스트 별 구조에 대해서 이해하기 쉬울 거 같습니다.

 

링크드 리스트 메인 프로그램 만들기

저는 코딩 공부를 하고 나면 직접 구현한 것을 이용해 실제로 사용해볼 수 있는 메인 프로그램을 만들어봅니다.

프로그램은 숫자를 입력해서 선택하는 방식으로 만들어 봤습니다!

1. 자료구조 선택 -> 2. 링크드 리스트 종류 선택 -> 3. 작업 선택 순서입니다.

 

import SLL
import DLL
import CDLL

while True:
    print('-' * 25)
    print('----- 자료구조 선택 -----')
    print('0. 종료')
    print('1. 링크드 리스트')
    print('-' * 25)
    selected = int(input('입력: '))
    if selected == 0:
        break
    elif selected == 1:
        while True:
            print('-' * 25)
            print('0. 뒤로가기')
            print('1. 싱글 링크드 리스트')
            print('2. 더블 링크드 리스트')
            print('3. 환형 링크드 리스트')
            print('-' * 25)
            selected = int(input('입력: '))
            if selected == 0:
                break
            elif selected == 1:
                list1 = SLL.SinglyLinkedList()
                print('-' * 25)
                print('생성 완료 : 싱글 링크드 리스트')

                while True:
                    print('0. 뒤로가기')
                    print('1. 노드 생성 및 삽입(append)')
                    print('2. 노드 생성 및 삽입(insert)')
                    print('3. 노드 삭제')
                    print('4. 노드 탐색')
                    print('5. 리스트 전체 출력')
                    print('-' * 25)

                    selected = int(input('입력: '))
                    
                    if selected == 0:
                        del list1
                        print('삭제 완료 : 싱글 링크드 리스트')
                        break
                    elif selected == 1:
                        data = input('삽입할 데이터: ')
                        node = list1.createNode(data)
                        list1.appendNode(node)
                    elif selected == 2:
                        data = input('삽입할 데이터: ')
                        node = list1.createNode(data)
                        loc = int(input('삽입할 위치: '))
                        list1.insertAfter(loc, node)
                    elif selected == 3:
                        loc = int(input('삭제할 노드 위치: '))
                        node = list1.getNodeByLocation(loc)
                        list1.removeNode(node)
                    elif selected == 4:
                        loc = int(input("찾을 위치: "))
                        node = list1.getNodeByLocation(loc)
                        print(f'{loc}위치 : {node.data}')
                    elif selected == 5:
                        size = list1.getSize()
                        for i in range(size):
                            node = list1.getNodeByLocation(i)
                            if i == 0:
                                print(f'Head : {node.data}', end="")
                            elif i == size-1:
                                print(f'Tail : {node.data}')
                                break
                            else:
                                print(f'{node.data}', end="")
                            print(f' -> ', end="")
                    print('-' * 25)
            elif selected == 2:
                list1 = DLL.DoublyLinkedList()
                print('-' * 25)
                print('생성 완료 : 더블 링크드 리스트')
                
                while True:
                    print('0. 뒤로가기')
                    print('1. 노드 생성 및 삽입(append)')
                    print('2. 노드 생성 및 삽입(insert)')
                    print('3. 노드 삭제')
                    print('4. 노드 탐색')
                    print('5. 리스트 전체 출력')
                    print('-' * 25)

                    selected = int(input('입력: '))
                    
                    if selected == 0:
                        del list1
                        print('삭제 완료 : 더블 링크드 리스트')
                        break
                    elif selected == 1:
                        data = input('삽입할 데이터: ')
                        node = list1.createNode(data)
                        list1.appendNode(node)
                    elif selected == 2:
                        data = input('삽입할 데이터: ')
                        node = list1.createNode(data)
                        loc = int(input('삽입할 위치: '))
                        list1.insertAfter(loc, node)
                    elif selected == 3:
                        loc = int(input('삭제할 노드 위치: '))
                        node = list1.getNodeByLocation(loc)
                        list1.removeNode(node)
                    elif selected == 4:
                        loc = int(input("찾을 위치: "))
                        node = list1.getNodeByLocation(loc)
                        print(f'{loc}위치 : {node.prev.data} << {node.data} >> {node.next.data}')
                    elif selected == 5:
                        size = list1.getSize()
                        for i in range(size):
                            node = list1.getNodeByLocation(i)
                            if i == 0:
                                if node.prev == None:
                                    print(f'Head : NULL << ', end="")
                                else:
                                    print(f'Head : {node.prev.data} << ', end="")

                                print(f'{node.data} >> ', end="")

                                if node.next == None:
                                    print(f'NULL', end="")
                                else:
                                    print(f'{node.next.data}', end="")
                            elif i == size-1:
                                if node.prev == None:
                                    print(f'Tail : NULL << ', end="")
                                else:
                                    print(f'Tail : {node.prev.data} << ', end="")

                                print(f'{node.data} >> ', end="")
                                
                                if node.next == None:
                                    print(f'NULL')
                                else:
                                    print(f'{node.next.data}')
                                break
                            else:
                                print(f'{node.prev.data} << {node.data} >> {node.next.data}', end="")
                            print(f' -> ', end="")
                    print('-' * 25)
            elif selected == 3:
                list1 = CDLL.CircularLinkedList()
                print('-' * 25)
                print('생성 완료 : 환형 링크드 리스트')
                
                while True:
                    print('0. 뒤로가기')
                    print('1. 노드 생성 및 삽입(append)')
                    print('2. 노드 생성 및 삽입(insert)')
                    print('3. 노드 삭제')
                    print('4. 노드 탐색')
                    print('5. 리스트 전체 출력')
                    print('-' * 25)

                    selected = int(input('입력: '))
                    
                    if selected == 0:
                        del list1
                        print('삭제 완료 : 환형 링크드 리스트')
                        break
                    elif selected == 1:
                        data = input('삽입할 데이터: ')
                        node = list1.createNode(data)
                        list1.appendNode(node)
                    elif selected == 2:
                        data = input('삽입할 데이터: ')
                        node = list1.createNode(data)
                        loc = int(input('삽입할 위치: '))
                        list1.insertAfter(loc, node)
                    elif selected == 3:
                        loc = int(input('삭제할 노드 위치: '))
                        node = list1.getNodeByLocation(loc)
                        list1.removeNode(node)
                    elif selected == 4:
                        loc = int(input("찾을 위치: "))
                        node = list1.getNodeByLocation(loc)
                        print(f'{loc}위치 : {node.prev.data} << {node.data} >> {node.next.data}')
                    elif selected == 5:
                        size = list1.getSize()
                        for i in range(size):
                            node = list1.getNodeByLocation(i)
                            print(f'{node.prev.data} << {node.data} >> {node.next.data}', end="")
                            print(f' -> ', end="")
                        print()
                    print('-' * 25)

엄청 기네요 ㄷㄷ

이번 글은 여기서 마무리하도록 하겠습니다. 감사합니다