초보몽키의 개발공부로그
강의노트 18. 자료구조 - LinkedList (링크드 리스트)
17 Apr 2017 |패스트캠퍼스 컴퓨터공학 입문 수업을 듣고 중요한 내용을 정리했습니다. 개인공부 후 자료를 남기기 위한 목적임으로 내용 상에 오류가 있을 수 있습니다.
linked list
- 강의자료
- 참고 생활코딩 - linked list
- 자료구조에서 가장 중요한 개념 중 하나 (doubly-linked-list와 함께 면접에 자주 나온다. node를 사용하여 구현)
- Array List와는 다르게 엘리먼트와 엘리먼트 간의 연결(link)을 이용해서 리스트를 구현한 것
- linked list에서 가장 중요한 것은 연결이 무엇인가를 파악하는 것
- python 의 경우 list 기본 자료형에 linked list 기능이 함께 포함되어 있다.
- array list에서는 엘리먼트라는 이름을 사용했지만 linked list와 같이 연결된 엘리먼트들은 노드(node, 마디, 교점의 의미) 혹은 버텍스(vertex, 정점, 꼭지점의 의미)라고 부른다.
dummy linked list
- 맨 앞에 dummy를 두어서 if문의 양을 줄인다.
- (실제 데이터를 지닌 노드가 아닌, 구현의 편의를 위해서 맨 앞에 두는 무의미한 노드)
- 노드를 단위로 한다. 노드는 자료와 다음 노드를 가리키는 참조값으로 구성되어 있다. 노드가 다음 노드로 아무것도 가리키지 않으면 리스트의 끝이다.
Node
- 노드는 자료와 다음 노드를 가리키는 참조값으로 구성되어 있다
- 자료구조를 이해하기 위해서는 노드에 충분히 익숙해져야 한다.
class Node:
def __init__(self, data):
self.data = data
self.next = None
dummy linked list ADT (인터페이스)
- 링크드 리스트 클래스 내에는 노드를 가르키는 1) 4개의 참조와 2) 데이터의 개수 만 존재한다.
- head : 맨 앞을 가르킨다.
- before : 현재 위치 전
- current : 현재 탐색위치
- tail : 맨 뒤를 가르킨다.
- num_of_data : 데이터의 총 개수
- 메소드 구현
- 생성자 : head, before, current, tail, num_of_data 초기화
- .append() : 맨 뒤에 노드 추가 (insert)
- .first() : 맨 앞의 노드 검색 (search)
- .next() : 다음 노트 검색 (search)
- .delete() : 현재 노드의 삭제 (delete)
dummy linked list 구현예시
LinkedList Class 정의
# Node 클래스 정의
class Node:
def __init__(self, data):
self.data = data
self.next = None
# LinkedList 클래스 (자료구조) 정의
class LinkedList:
# 초기화 메소드
def __init__(self):
dummy = Node("dummy")
self.head = dummy
self.tail = dummy
self.current = None
self.before = None
self.num_of_data = 0
# append 메소드 (insert - 맨 뒤에 노드 추가, tail과 node의 next, 데이터 개수 변경)
def append(self, data):
new_node = Node(data)
self.tail.next = new_node
self.tail = new_node
self.num_of_data += 1
# delete 메소드 (delete - current 노드 삭제, 인접 노드의 current, next 변경, 데이터 개수 변경)
def delete(self):
pop_data = self.current.data
if self.current is self.tail:
self.tail = self.before
self.before.next = self.current.next
self.current = self.before # 중요 : current가 next가 아닌 before로 변경된다.
#
self.num_of_data -= 1
return pop_data
# first 메소드 (search1 - 맨 앞의 노드 검색, before, current 변경)
def first(self):
if self.num_of_data == 0: # 데이터가 없는 경우 첫번째 노드도 없기 때문에 None 리턴
return None
self.before = self.head
self.current = self.head.next
return self.current.data
# next 메소드 (search2 - current 노드의 다음 노드 검색, 이전에 first 메소드가 한번은 실행되어야 함)
def next(self):
if self.current.next == None:
return None
self.before = self.current
self.current = self.current.next
return self.current.data
def size(self):
return self.num_of_data
테스트 코드
if __name__ = '__main__':
l_list = LinkedList()
l_list.append(5)
l_list.append(2)
l_list.append(1)
l_list.append(2)
l_list.append(7)
l_list.append(2)
l_list.append(11)
print('first :', l_list.first()) # first : 5
print('next :', l_list.next()) # next : 2
print('size :', l_list.size()) # size : 7
print('delete :', l_list.delete()) # delete : 2
print('size :', l_list.size()) # size : 6
print('current:', l_list.current.data)# current: 5
print('tail:', l_list.tail.data) # tail: 11
print('first :', l_list.first()) # first : 5
print('next :', l_list.next()) # next : 1
print('next :', l_list.next()) # next : 2
print('next :', l_list.next()) # next : 7
# 전체 노드 data 표시하기
data = l_list.first()
if data:
print(data, end=' ')
while True:
data = l_list.next()
if data:
print(data, end= ' ')
else:
break
# 5 1 2 7 2 11
# 2만 삭제하기
data = l_list.first()
if data and data == 2:
l_list.delete()
print('deleted', end=' ')
else:
print(data, end= ' ')
while True:
data = l_list.next()
if data == 2:
l_list.delete()
print('deleted', end=' ')
elif data:
print(data, end=' ')
else:
break
# 5 1 deleted 7 deleted 11