[자료구조] Week 2: 연결 리스트

Day 1: 연결 리스트의 개요

강의 내용:
- 연결 리스트의 정의와 특징
  - 연결 리스트의 개념과 필요성
  - 배열과 연결 리스트의 비교
- 연결 리스트의 종류
  - 단일 연결 리스트
  - 이중 연결 리스트
  - 원형 연결 리스트
실습:
- 연결 리스트의 개념을 설명하는 예제

# 연결 리스트의 기본 개념 설명
# 배열과 연결 리스트 비교
# 배열: 요소가 연속된 메모리 위치에 저장됨
# 연결 리스트: 요소가 노드로 저장되고, 각 노드는 다음 노드를 가리키는 포인터를 가짐

Day 2: 단일 연결 리스트

강의 내용:
- 단일 연결 리스트의 구조
  - 노드의 정의
  - 단일 연결 리스트의 구성
- 단일 연결 리스트의 기본 연산
  - 노드 삽입, 삭제, 검색
실습:
- 단일 연결 리스트를 구현하는 예제

# 단일 연결 리스트의 노드 정의
class Node:
    def __init__(self, data):
        self.data = data
        self.next = None

# 단일 연결 리스트 정의
class SinglyLinkedList:
    def __init__(self):
        self.head = None

    # 노드 삽입 (리스트의 끝에 삽입)
    def append(self, data):
        new_node = Node(data)
        if not self.head:
            self.head = new_node
            return
        last = self.head
        while last.next:
            last = last.next
        last.next = new_node

    # 노드 삭제
    def delete(self, key):
        temp = self.head
        if temp and temp.data == key:
            self.head = temp.next
            temp = None
            return
        prev = None
        while temp and temp.data != key:
            prev = temp
            temp = temp.next
        if temp is None:
            return
        prev.next = temp.next
        temp = None

    # 노드 검색
    def search(self, key):
        current = self.head
        while current:
            if current.data == key:
                return True
            current = current.next
        return False

    # 리스트 출력
    def display(self):
        current = self.head
        while current:
            print(current.data, end=" -> ")
            current = current.next
        print("None")

# 단일 연결 리스트 사용 예제
sll = SinglyLinkedList()
sll.append(1)
sll.append(2)
sll.append(3)
sll.display()  # 1 -> 2 -> 3 -> None
print("Search 2:", sll.search(2))  # Search 2: True
sll.delete(2)
sll.display()  # 1 -> 3 -> None

Day 3: 이중 연결 리스트

강의 내용:
- 이중 연결 리스트의 구조
  - 노드의 정의
  - 이중 연결 리스트의 구성
- 이중 연결 리스트의 기본 연산
  - 노드 삽입, 삭제, 검색
실습:
- 이중 연결 리스트를 구현하는 예제

# 이중 연결 리스트의 노드 정의
class DNode:
    def __init__(self, data):
        self.data = data
        self.prev = None
        self.next = None

# 이중 연결 리스트 정의
class DoublyLinkedList:
    def __init__(self):
        self.head = None

    # 노드 삽입 (리스트의 끝에 삽입)
    def append(self, data):
        new_node = DNode(data)
        if not self.head:
            self.head = new_node
            return
        last = self.head
        while last.next:
            last = last.next
        last.next = new_node
        new_node.prev = last

    # 노드 삭제
    def delete(self, key):
        temp = self.head
        while temp and temp.data != key:
            temp = temp.next
        if temp is None:
            return
        if temp.prev:
            temp.prev.next = temp.next
        if temp.next:
            temp.next.prev = temp.prev
        if temp == self.head:
            self.head = temp.next
        temp = None

    # 노드 검색
    def search(self, key):
        current = self.head
        while current:
            if current.data == key:
                return True
            current = current.next
        return False

    # 리스트 출력 (정방향)
    def display(self):
        current = self.head
        while current:
            print(current.data, end=" <-> ")
            current = current.next
        print("None")

    # 리스트 출력 (역방향)
    def display_reverse(self):
        current = self.head
        while current.next:
            current = current.next
        while current:
            print(current.data, end=" <-> ")
            current = current.prev
        print("None")

# 이중 연결 리스트 사용 예제
dll = DoublyLinkedList()
dll.append(1)
dll.append(2)
dll.append(3)
dll.display()  # 1 <-> 2 <-> 3 <-> None
dll.display_reverse()  # 3 <-> 2 <-> 1 <-> None
print("Search 2:", dll.search(2))  # Search 2: True
dll.delete(2)
dll.display()  # 1 <-> 3 <-> None

Day 4: 원형 연결 리스트

강의 내용:
- 원형 연결 리스트의 구조
  - 노드의 정의
  - 원형 연결 리스트의 구성
- 원형 연결 리스트의 기본 연산
  - 노드 삽입, 삭제, 검색
실습:
- 원형 연결 리스트를 구현하는 예제

# 원형 연결 리스트의 노드 정의
class CNode:
    def __init__(self, data):
        self.data = data
        self.next = None

# 원형 연결 리스트 정의
class CircularLinkedList:
    def __init__(self):
        self.head = None

    # 노드 삽입 (리스트의 끝에 삽입)
    def append(self, data):
        new_node = CNode(data)
        if not self.head:
            self.head = new_node
            new_node.next = self.head
            return
        last = self.head
        while last.next != self.head:
            last = last.next
        last.next = new_node
        new_node.next = self.head

    # 노드 삭제
    def delete(self, key):
        if self.head is None:
            return
        temp = self.head
        prev = None
        while True:
            if temp.data == key:
                if prev:
                    prev.next = temp.next
                else:
                    self.head = temp.next
                    last = self.head
                    while last.next != temp:
                        last = last.next
                    last.next = self.head
                temp = None
                return
            prev = temp
            temp = temp.next
            if temp == self.head:
                break

    # 노드 검색
    def search(self, key):
        current = self.head
        if current is None:
            return False
        while True:
            if current.data == key:
                return True
            current = current.next
            if current == self.head:
                return False

    # 리스트 출력
    def display(self):
        current = self.head
        if current is None:
            print("List is empty")
            return
        while True:
            print(current.data, end=" -> ")
            current = current.next
            if current == self.head:
                break
        print(current.data, "(head)")

# 원형 연결 리스트 사용 예제
cll = CircularLinkedList()
cll.append(1)
cll.append(2)
cll.append(3)
cll.display()  # 1 -> 2 -> 3 -> 1 (head)
print("Search 2:", cll.search(2))  # Search 2: True
cll.delete(2)
cll.display()  # 1 -> 3 -> 1 (head)

Day 5: 연결 리스트의 활용

강의 내용:
- 연결 리스트의 실제 활용 사례
  - 스택과 큐의 구현
  - 폴리노미얼 연산
- 연결 리스트를 사용한 알고리즘
  - 정렬 및 검색 알고리즘
실습:
- 연결 리스트를 활용한 예제 작성

# 연결 리스트를 사용한 스택 구현
class Stack:
    def __init__(self):
        self.head = None

    def push(self, data):
        new_node = Node(data)
        new_node.next = self.head
        self.head = new_node

    def pop(self):
        if self.head is None:
            return None
        popped = self.head.data
        self.head = self.head.next
        return popped

    def display(self):
        current = self.head
        while current:
            print(current.data, end=" -> ")
            current = current.next
        print("None")

# 스택 사용 예제
stack = Stack()
stack.push(1)
stack.push(2)
stack.push(3)
stack.display()  # 3 -> 2 -> 1 -> None
print("Popped:", stack.pop())  # Popped: 3
stack.display()  # 2 -> 1 -> None

# 연결 리스트를 사용한 큐 구현
class Queue:
    def __init__(self):
        self.front = None
        self.rear = None

    def enqueue(self, data):
        new_node = Node(data)
        if self.rear is None:
            self.front = self.rear = new_node
            return
        self.rear.next = new_node
        self.rear = new_node

    def dequeue(self):
        if self.front is None:
            return None
        dequeued = self.front.data
        self.front = self.front.next
        if self.front is None:
            self.rear = None
        return dequeued

    def display(self):
        current = self.front
        while current:
            print(current.data, end=" -> ")
            current = current.next
        print("None")

# 큐 사용 예제
queue = Queue()
queue.enqueue(1)
queue.enqueue(2)
queue.enqueue(3)
queue.display()  # 1 -> 2 -> 3 -> None
print("Dequeued:", queue.dequeue())  # Dequeued: 1
queue.display()  # 2 -> 3 -> None

Day 6: 연결 리스트의 장단점 및 한계

강의 내용:
- 연결 리스트의 장점
  - 동적 크기 조절
  - 메모리 효율성
- 연결 리스트의 단점 및 한계
  - 순차 접근의 비효율성
  - 메모리 오버헤드
실습:
- 연결 리스트의 장단점을 설명하고, 실제 코드로 비교

# 연결 리스트의 장단점 비교 예제

# 장점: 동적 크기 조절
sll = SinglyLinkedList()
sll.append(1)
sll.append(2)
sll.append(3)
sll.display()  # 1 -> 2 -> 3 -> None

# 단점: 순차 접근의 비효율성
def find_nth_node(head, n):
    current = head
    count = 0
    while current:
        if count == n:
            return current.data
        count += 1
        current = current.next
    return None

print("2번째 노드:", find_nth_node(sll.head, 1))  # 2번째 노드: 2

Day 7: 종합 연습 및 프로젝트

강의 내용:
- 연결 리스트를 사용한 종합 연습 문제 풀이
  - 다양한 연결 리스트 관련 문제
  - Q&A 세션
- 미니 프로젝트
  - 연결 리스트를 활용한 간단한 프로그램 구현
  - 예: 링크드 리스트 기반의 Todo List
실습:
- 종합 연습 문제 풀기
- 미니 프로젝트 작성 및 발표

# 연습 문제 1: 단일 연결 리스트에서 중간 노드 찾기
def find_middle_node(head):
    slow = head
    fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
    return slow.data

sll = SinglyLinkedList()
sll.append(1)
sll.append(2)
sll.append(3)
sll.append(4)
sll.append(5)
print("중간 노드:", find_middle_node(sll.head))  # 중간 노드: 3

# 미니 프로젝트 예제: 링크드 리스트 기반 Todo List
class TodoList:
    def __init__(self):
        self.tasks = SinglyLinkedList()

    def add_task(self, task):
        self.tasks.append(task)

    def remove_task(self, task):
        self.tasks.delete(task)

    def display_tasks(self):
        self.tasks.display()

# Todo List 사용 예제
todo_list = TodoList()
todo_list.add_task("Task 1")
todo_list.add_task("Task 2")
todo_list.add_task("Task 3")
todo_list.display_tasks()  # Task 1 -> Task 2 -> Task 3 -> None
todo_list.remove_task("Task 2")
todo_list.display_tasks()  # Task 1 -> Task 3 -> None

이 강의는 파이썬의 자료구조 중 연결 리스트를 익히는 것을 목표로 하며, 각 강의는 이론과 실습을 포함합니다. 다음 주차에 대한 상세 강의를 원하시면 말씀해 주세요!

저작자표시 비영리 변경금지

'자료구조' 카테고리의 다른 글

[자료구조] Week 6: 트리 I - 트리의 개념과 이진 트리 (0)	2024.06.01
[자료구조] Week 5: 해시 테이블 (0)	2024.06.01
[자료구조] Week 4: 우선순위 큐와 힙 (0)	2024.06.01
[자료구조] Week 3: 스택과 큐 (0)	2024.06.01
[자료구조] Week 1: 자료구조 개요 및 배열 (0)	2024.06.01

Python 개발자

[자료구조] Week 2: 연결 리스트

'자료구조' 카테고리의 다른 글

티스토리툴바

[자료구조] Week 2: 연결 리스트

'자료구조' 카테고리의 다른 글

관련글

티스토리툴바