프로그래밍/자료구조6 파이썬으로 이중연결리스트를 만들어보자! (추가 연산, 탐색 연산) 지난 시간에는 단순연결리스트를 만들어보았습니다. 이번에는 연결이 이중으로 된 이중연결리스트를 만들어보겠습니다. 이중연결리스트의 노드는 자신을 기준으로 다음에 있는 노드가 next 노드, 이전을 prev 노드라고 하겠습니다. 이를 그림으로 그려보면 다음과 같습니다. head node와 tail node 부분을 보면 None이 있는데 head node의 이전이 없어서 None이며, tail node도 다음이 없어서 None으로 표시한 것입니다. 각 노드를 보면 data와 next, prev 총 3가지 속성이 있는 것을 알 수 있습니다. 그래서 Node class에는 3개의 인스턴스 변수가 들어가게 됩니다. 코드로 알아보면 다음과 같습니다. class Node: def __init__(self, data): .. 2023. 1. 29. 단순연결리스트로 스택 구현하기(Stack 자료구조, FILO : first in Last out) 지난 번에 단순 연결리스트를 구현해보았고 이번에는 이 단순 연결리스트를 이용하여 먼저 들어온 친구는 가장 나중에 나가는 Stack이라는 자료구조를 만들어보려고 합니다. 파이썬에서는 이미 스택 자료구조를 리스트 자료형(동적배열)을 이용하여 구현이 되어있습니다. 파이썬으로 연결리스트 만들기 4탄 : 단순 연결리스트 삭제연산 (맨 앞 노드 삭제 / 맨 뒤 노드 삭 이번에는 단순 연결리스트에서 노드를 삭제하는 방법을 알아보겠습니다. 노드를 삭제할 때는 맨 앞 노드를 삭제 / 맨 뒤 노드 삭제 / 중간 노드 삭제로 경우를 나눌 수 있습니다. 그렇다면 삭제 c-i-s.tistory.com 우선 지난번에 만든 단순 연결리스트의 시간복잡도를 알아보겠습니다. (추가, 삽입, 삭제, 탐색) 추가연산 O(1) 삽입연산 O(.. 2023. 1. 29. 파이썬으로 연결리스트 만들기 4탄 : 단순 연결리스트 삭제연산 (맨 앞 노드 삭제 / 맨 뒤 노드 삭제 / 중간 노드 삭제 방법) 이번에는 단순 연결리스트에서 노드를 삭제하는 방법을 알아보겠습니다. 노드를 삭제할 때는 맨 앞 노드를 삭제 / 맨 뒤 노드 삭제 / 중간 노드 삭제로 경우를 나눌 수 있습니다. 그렇다면 삭제할 노드가 맨 앞인지, 맨 뒤인지, 중간인지 판단할 수 있어야 합니다. 만약 잘 판단했다고 치고 맨 앞 노드를 삭제하는 경우는 다음과 같습니다. 맨 앞 삭제 reference head -> -> -> .... data a b c d .... i) 맨 앞 노드 삭제 방법 -> head.next가 head가 된다. 맨 앞 삭제 reference head -> -> .... data a b c d .... 그러면 단순 연결리스트는 head 부터 시작하니까 a가 자연스럽게 끊어집니다. 방법을 알았으면 코드를 작성해야합니다. .. 2023. 1. 1. 파이썬으로 연결리스트 만들기 3탄 : 단순 연결리스트 삽입 연산(원하는 곳에 삽입하자! / 맨 뒤에 삽입 / 맨 앞에 삽입 / 중간에 삽입) 지난 시간 단순 연결리스트의 추가 연산에 대해서 알아보았습니다. 파이썬으로 연결리스트 만들기 2탄 : 단순 연결리스트 추가 연산 (연결리스트 자동 출력 만들기) 이전에 만들었던 코드에 이어서 이번에는 추가 연산을 하는 기능을 추가해보겠습니다. 추가 연산은 두 가지 경우의 수가 있음을 유추해볼 수 있습니다. 1. 이미 있는 연결리스트의 뒤에 추가하 c-i-s.tistory.com 이번에는 원하는 위치에 삽입하는 과정에 대해서 알아보도록 하겠습니다. 그림으로 우선 알아보도록 하겠습니다. 원리는 간단합니다. 삽입할 위치에 노드를 연결시켜주면 됩니다. 이렇게만 말만하면 너무 쉽게 느껴집니다. 이 과정을 조금 더 자세하게 알아보겠습니다. 위 그림 대로라면? 1) 삽입 할 위치와 리스트에 연결할 값을 입력받는다. .. 2022. 12. 6. 파이썬으로 연결리스트 만들기 2탄 : 단순 연결리스트 추가 연산 (연결리스트 자동 출력 만들기) 이전에 만들었던 코드에 이어서 이번에는 추가 연산을 하는 기능을 추가해보겠습니다. 추가 연산은 두 가지 경우의 수가 있음을 유추해볼 수 있습니다. 1. 이미 있는 연결리스트의 뒤에 추가하는 경우 2. 연결리스트가 비어있을 때 추가하는 경우 이미 있는 연결리스트 뒤에 추가하는 경우 동작 과정입니다. 1) 새 노드를 생성한다. 2) tail node의 다음이 새 노드를 가리킨다. 3) 새 노드는 tail node가 된다. 비어있는 연결리스트에 추가하는 경우 동작 과정입니다. 1) 새 노드를 생성한다. 2) 새 노드가 head node가 된다. 3) 새노드가 tail node가 된다. 그렇다면 연결리스트가 비어있는지 있는지 판단해야합니다. 이는 조건문으로 해결해야합니다. head 노드가 비어있다면 그 연결리스.. 2022. 12. 4. 파이썬으로 연결리스트 만들기 1탄(자료구조 / 단순 연결리스트 / 이중 연결리스트 / 추가 / 삽입 / 삭제 / 접근) 파이썬의 클래스에 대해서 익숙해지는 시간을 가지기 위해서 간단한 자료구조인 Linked List, 연결리스트에 대해서 알아보도록 하겠습니다. 연결리스트는 각 노드를 선으로 연결한 것이라 할 수 있습니다. 그림으로 표현하면 다음과 같습니다. 저 그림을 조금 더 자세히 표현하면 이렇게 표현할 수 있고 이 그림은 단방향으로 연결되어 있어서 단순 연결리스트 또는 Singly Linked List 라고도 합니다. 저기 사각형 하나는 노드(Node)라고 합니다. 연결리스트는 노드들이 연결된 것이고 노드에는 값과 다음 노드를 가리키는 정보가 들어있습니다. 노드가 많이 필요할 수 있으니까 이를 class로 만들면 편합니다. 클래스를 만들 때는 속성과 행동을 봐야합니다. Node 클래스의 속성은 값과 다음 노드를 가리키.. 2022. 12. 4. 이전 1 다음
