• 개요

연결 리스트

추상적 자료구조 Abstract Dat Structures

: 자료의 내부 구현은 숨겨두고 밖에서 보이는 것들 두 가지를 제공하는 것

• Data

  • ex. 정수, 문자열, 레코드, …

• A set of operations

  • 삽입, 삭제, 순회, …
  • 정렬, 탐색, … (class 사용 예정)

• 기본적 연결 리스트

  

  

  비어 있는 연결 리스트

  • Node
    • Data
    • Link (next)
    • Node 내의 데이터는 다른 구조로 이루어질 수 있음 ex. 문자열, 레코드, 또 다른 연결 리스트 등
  • Head : 리스트의 맨 앞 (67)
  • Tail : 리스트의 맨 끝 (58)

  • of nodes (3)

배열과 비교한 연결 리스트

• 👎 인덱싱 ❌ → 노드 지칭하는 데에 길이에 비례하는 시간 소요..
• 👍 삽입과 삭제가 유연하다는 점, 병합 쉬움

자료 구조 정의 (2개의 클래스)

1. Node

   • Data
   • Link (next)

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

생성자constructor 하나만 해봄

1. LinkedList

   class LinkedList:
       def __init__(self): # 인자 X
           self.nodeCount = 0 # 초기화
           self.head = None
           self.tail = None
   

연산 정의

1. 특정 원소 참조 (k번째)

• 1, 2, 3, … index 부여 (∵ 0은 다르게 이용할 것)

# k번째 인자
def getAt(self, pos): # 클래스 LinkedList의 method
    if pos <= 0 or pos > self.nodeCount: # k번째 노드 없음!
        return None
    i = 1
    curr = self.head # 첫번째 노드
    while i < pos:
        curr = curr.next
        i += 1
    return curr

2. 리스트 순회

• 잘못된 코드