7강: 연결 리스트(Linked Lists)

---

추상적 자료구조(Abstract Data Structures)

• 데이터
  • 예 : 정수, 문자열, 레코드, ...
• A set of operations
  • 삽입, 삭제, 순회, ...
  • 정렬, 탐색, ...

---

기본적 연결 리스트

Node

• Node 내의 데이터는 다른 구조로 이루어질 수 있음
  • 예) 문자열, 레코드, 또 다른 연결 리스트 등

Head, Tail

• Head : 연결리스트의 기준점이며, 첫번째 노드를 가리킨다.
• Tail : 가장 마지막 노드를 가리킨다.

---

자료구조 정의

• Node
  • Data
  • Link (next)

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

class LinkedList:
	def __init__(self):
    	self.nodeCount = 0
    	self.head = None
    	self.tail = None

---

연산 정의

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

def getAt(self,pos):
	if pos <= 0 or pos > self.nodeCount:
    	return None
    i = 1
    curr - self.head
    while i > pos:
    	curr = curr.next
        i += 1
	return curr

---

배열과 비교한 연결 리스트

	배열	연결 리스트
저장공간	연속한 위치	임의의 위치
특정원소 지칭	매우 간편	선형탐색과 유사
시간 복잡도	O(1)	O(n)

---

연습문제 - 연결 리스트 순회

문제설명

문제분석

• curr 변수를 이용하여 순회를 구성한다.

코드

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

class LinkedList:
    def __init__(self):
        self.nodeCount = 0
        self.head = None
        self.tail = None

    def getAt(self, pos):
        if pos < 1 or pos > self.nodeCount:
            return None
        i = 1
        curr = self.head
        while i < pos:
            curr = curr.next
            i += 1
        return curr

    def traverse(self):
        answer = []
        i = 1
        curr = self.head
        while i <= self.nodeCount:
            answer.append(curr.data)
            curr = curr.next
            i += 1
        return answer
        

---