자료구조와 함께 배우는 알고리즘 입문 [파이썬] - 8장. 리스트

파이썬의 리스트는 연결리스트의 자료구조가 아니라 모든 원소를 연속으로 메모리에 배치하는 배열로 내부에서 구현함

8-1. 연결리스트

• 데이터가 순서대로 나열되고 각 데이터가 화살표로 연결
• 각각의 원소를 노드
• 노드가 갖고있는 것은 데이터와 뒤쪽 노드를 참조하는 포인터
• 맨 앞: 머리노드, 맨 끝: 꼬리노드

---

8-2. 포인터를 이용한 연결리스트

• Node는 데이터용 필드 data와는 별도로 자신과 같은 클래스형의 인스턴스를 참조하기 위한 참조용 필드 next를 갖는다.

  이처럼 자신과 같은 형의 인스턴스를 참조하는 필드가 있는 구조를 자기참조형이라고 함

• 연결리스트 참고 문서 링크
  [CS-자료구조] 포인터를 이용한 연결리스트 with python

def search(self, data: Any) -> int:
        """data와 값이 같은 노드를 검색"""
        cnt = 0
        ptr = self.head
        while ptr is not None:
            if ptr.data == data:
                self.current = ptr
                return cnt
            cnt += 1
            ptr = ptr.next
        return -1

def add_last(self, data: Any):
        """맨 끝에 노드를 삽입"""
        if self.head is None :    # 리스트가 비어 있으면
            self.add_first(data)  # 맨앞에 노드 삽입
        else:
            ptr = self.head
            while ptr.next is not None:
                ptr = ptr.next  # while문을 종료할 때 ptr은 꼬리 노드를 참조
            ptr.next = self.current = Node(data, None)
            self.no += 1

rom enum import Enum
from linked_list import LinkedList

Menu = Enum('Menu', ['머리에노드삽입', '꼬리에노드삽입', '머리노드삭제',
                     '꼬리노드삭제', '주목노드출력', '주목노드이동',
                     '주목노드삭제', '모든노드삭제', '검색', '멤버십판단',
                     '모든노드출력', '스캔', '종료',])

def select_Menu() -> Menu:
    """메뉴 선택"""
    s = [f'({m.value}){m.name}' for m in Menu]
    while True:
        print(*s, sep='  ', end='')
        n = int(input(': '))
        if 1 <= n <= len(Menu):
            return Menu(n)

lst = LinkedList()  # 연결 리스트를 생성

while True:
    menu = select_Menu()  # 메뉴 선택

    if menu == Menu.머리에노드삽입:  # 맨 앞에 노드 삽입
        lst.add_first(int(input('머리에 넣을 값을 입력하세요.: ')))

    elif menu == Menu.꼬리에노드삽입:  # 맨 끝에 노드 삽입
        lst.add_last(int(input('꼬리에 넣을 값을 입력하세요.: ')))

    elif menu == Menu.머리노드삭제:  # 맨 앞 노드 삭제
        lst.remove_first()

    elif menu == Menu.꼬리노드삭제:  # 맨 끝 노드 삭제
        lst.remove_last()

    elif menu == Menu.주목노드출력:  # 주목 노드 출력
        lst.print_current_node()

    elif menu == Menu.주목노드이동:  # 주목 노드를 한 칸 뒤로 이동
        lst.next()

    elif menu == Menu.주목노드삭제:  # 주목 노드 삭제
        lst.remove_current_node()

    elif menu == Menu.모든노드삭제:  # 모든 노드를 삭제
        lst.clear()

    elif menu == Menu.검색:  # 노드를 검색
        pos = lst.search(int(input('검색할 값을 입력하세요.: ')))
        if pos >= 0:
            print(f'그 값의 데이터는 {pos + 1}번째에 있습니다.')
        else:
            print('해당 데이터가 없습니다.')

    elif menu == Menu.멤버십판단:  # 멤버십 판단
        print('그 값의 데이터는 포함되어' + (' 있습니다.' if int(input('멤버십 판단할 값을 입력하세요.: ')) in lst else ' 있지 않습니다.'))

    elif menu == Menu.모든노드출력:  # 모든 노드 출력
        lst.print()

    elif menu == Menu.스캔:  # 모든 노드 스캔
        for e in lst:
            print(e)

    else:  # 종료
        break

---

8-3. 커서를 이용한 연결리스트

• 포인터를 이용한 연결리스트는 ‘노드를 삽입, 삭제할 때 데이터를 이동하지 않고 처리’하는 특징
• 하지만 노드를 삽입, 삭제할때마다 내부에서 노드용 인스턴스를 생성하고 소멸한다.
• 뒤쪽 포인터는 뒤쪽 노드가 저장되는 원소의 인덱스. 인덱스로 나타낸 포인터를 커서
• 삽입과 삭제에 따른 원소 이동이 불필요하다는 점에서 포인터 리스트와 다르다.

---

8-4. 원형 이중 연결리스트

• 꼬리노드가 다시 머리노드를 가시키는 원형모양
• 뒤쪽노드, 앞쪽노드에 대한 포인터 가져서 이중 연결리스트

• 연결리스트 비교
  

• 저장된 노드 없을때 : 위치값 None 반환
• 저장된 노드 있을 때 (head에서부터 탐색)
  • 출력과 동일한 방식으로 노드 이동
  • 찾으려는 데이터를 가진 노드가 발견되면 이동 중단
  • 값을 찾으면 해당 노드가 몇번째인지 반환
  • link가 tail인 경우 중단
• 저장된 노드 있을때 ( tail에서부터 탐색)
  • 출력과 동일한 방식으로 노드 이동
  • 찾으려는 데이터를 가진 노드가 발견되면 이동 중단
  • 값을 찾으면 해당 노드가 몇번때인지 반환 ( 위치는 초기값을 -1로 주고, 진행할 때마다 1씩 감소)
  • link가 head인 경우 중단

# 원형 이중 링크드 리스트
class DCLinkedList:
    # D_C_L_List에서 쓸 노드
    class Node:
        def __init__(self, v, n=None, p=None):
            self.value = v  # 저장된 데이터
            self.next = n  # 다음 노드 가리키는 변수
            self.prev = p  # 이전 노드 가리키는 변수

    # D_C_L_List에서 필요한 변수
    def __init__(self):
        self.head = None  # 첫 생성시 내부에는 노드가 없음
        self.tail = None

    # head로 삽입. v : 데이터
    def insertNodeBefore(self, v):
        # 없을 경우
        if self.head is None:
            self.head = self.Node(v)
            self.tail = self.head  # 같은 노드를 가리킴
        else:
            # 기존 head.prev를 새 노드로 지정(새 노드의 prev는 tail, next는 head로 지정)
            self.head.prev = self.Node(v, n=self.head, p=self.tail)
            self.head = self.head.prev  #head를 새 노드로 변경
            self.tail.next = self.head   #tail.next를 새 head로 업데이트

    # tail로 삽입. v : 데이터
    def insertNodeAfter(self, v):
        # 없을 경우
        if self.tail is None:
            self.tail = self.Node(v)
            self.head = self.tail  # 같은 노드를 가리킴
        else:
            # 기존 tail.next를 새 노드로 지정(새 노드의 prev는 tail, next는 head로 지정)
            self.tail.next = self.Node(v, p=self.tail, n=self.head)
            self.tail = self.tail.next  #tail을 새 노드로 변경
            self.head.prev = self.tail #head.prev를 새 tail로 업데이트

    def printNodeBefore(self):
        # 데이터가 없을 때
        if self.head is None:
            print("저장된 데이터가 없음")
            return
        else:
            print("<현재 리스트 구조>", end='\t')
            link = self.head  # 처음은 head를 지정. 이후부터는 현 노드의 next를 지정

            # link가 가리키는 노드가 없을 때까지 반복
            # None,0,""는 조건판단에서 False 처리, 그 외는 True로 처리
            while link:
                print(link.value, '<->', end=' ')
                if link == self.tail: #link가 tail일 경우 멈추기
                    break
                link = link.next  # link를 현 위치 노드의 next로 변경
            print()  # 줄바꿈 용

    def printNodeAfter(self):
        # 데이터가 없을 때
        if self.tail is None:
            print("저장된 데이터가 없음")
            return
        else:
            print("<현재 리스트 구조>", end='\t')
            link = self.tail

            while link:
                print(link.value, '<->', end=' ')
                if link == self.head: #link가 head일 경우 멈추기
                    break
                link = link.prev  # link를 현 위치 노드의 next로 변경
            print()  # 줄바꿈 용

    # head로 삭제
    def deleteNodeBefore(self):
        # 없을 경우 - > 스킵
        if self.head is None:
            print("삭제할 노드가 없습니다.")
            return
        else:
            #현재 head가 가리키는 노드의 next를 새로운 head로 지정
            self.head = self.head.next
            self.head.prev = self.tail  #새로운 head.prev를 tail로 지정
            self.tail.next = self.head  #tail.next를 head로 지정

    # tail로 삭제
    def deleteNodeAfter(self):
        # 없을 경우 - > 스킵
        if self.tail is None:
            print("삭제할 노드가 없습니다.")
            return
        else:
            #현재 tail이 가리키는 노드의 prev를 새로운 tail로 지정
            self.tail = self.tail.prev
            self.tail.next = self.head #새로운 tail.next를 head로 지정
            self.head.prev = self.tail #head.prev를 tail로 지정

    # head로 조회(탐색)
    def searchNodeBefore(self, v):
        # 데이터가 없을 때
        if self.head is None:
            print("저장된 데이터가 없음")
            return
        else:
            link = self.head  # 처음은 head를 지정. 이후부터는 현 노드의 next를 지정
            index = 0  # 몇 번째 노드인지 기록
            while link:
                # 내가 찾는 노드인지 확인
                if v == link.value:
                    return index  # 위치를 반환
                else:
                    link = link.next  # link를 현 위치 노드의 next로 변경
                    index += 1  # 위치값 1 증가
                    if link == self.tail: #link가 tail일 경우 멈추기
                        break
            # 여기까지 왔다 == 해당 v값을 가진 노드가 없다.

    # tail로 조회(탐색)
    def searchNodeAfter(self, v):
        # 데이터가 없을 때
        if self.tail is None:
            print("저장된 데이터가 없음")
            return
        else:
            link = self.tail
            index = -1  # 몇 번째 노드인지 기록
            while link:
                # 내가 찾는 노드인지 확인
                if v == link.value:
                    return index  # 위치를 반환
                else:
                    link = link.prev  # link를 현 위치 노드의 prev로 변경
                    index -= 1  # 위치값 1 감소
                    if link == self.head: #link가 head일 경우 멈추기
                        break
            # 여기까지 왔다 == 해당 v값을 가진 노드가 없다.