[자료구조] 연결 리스트(Linked Lists) (1)

연결 리스트(Linked Lists)

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

자료구조의 내부구현은 숨겨두고 밖에서 보이는 두가지(Data, A set of operations)를 제공하는 자료구조

• Data
  • ex. 정수, 문자열, 레코드, ...
• A set of operations(일련의 연산들)
  • 삽입, 삭제, 순회, ...
  • 정렬, 탐색, ...

연결 리스트

앞에 있는 것이 뒤에 있는 것을 가리키도록 되어 있는 리스트

• Node
  • data와 Link(next)가 하나씩 들어 있는 곳
  • Node에는 데이터 뿐만아니라 다음 위치를 나타내는 Link도 함께 존재
  • Node 내의 데이터는 다른 구조로 이루어질 수 있다.
    ex. 문자열, 레코드, 또 다른 연결 리스트 등
• 리스트의 맨 앞은 알아야 다른 노드를 찾아갈 수 있다.
• 용어
  • Head: 리스트의 맨 앞
  • Tail: 리스트의 맨 끝
  • $\#$ of nodes: 노드의 수
• 리스트 데이터와 리스트에 가해질 수 있는 연산들을 모으면 그것이 연결 리스트의 추상적 자료구조이다.

자료 구조 정의 (Node class + 연산 class)

1. Node class (Data+Link)

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

2. 연산 class

• 연산 정의

1. 특정 원소 참조 (k번째)
2. 리스트 순회
3. 길이 얻어내기
4. 원소 삽입
5. 원소 삭제
6. 두 리스트 합치기

• 특정 원소 참조
  pos번째에 있는 노드를 찾아서 노드 그대로 반환

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

배열 vs 연결 리스트

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