연결 리스트(Linked List)
Linked List 구조
- 연결 리스트라고도 함
- 배열은 순차적으로 연결된 공간에 데이터를 나열하는 데이터 구조
- 연결 리스트는 떨어진 곳에 존재하는 데이터를 화살표로 연결해서 관리하는 데이터 구조
- 본래 C언어에서는 주요한 데이터 구조이지만, 파이썬은 리스트 타입이 링크드 리스트의 기능을 모두 지원
- 미리 데이터 크기를 예약해 놓지 않고, 필요할 때마다 추가추가 하는 것 : 배열의 단점을 극복한 구조
Linked List 기본 구조와 용어
- 노드(Node): 데이터 저장 단위 (데이터값, 포인터) 로 구성
- 포인터(pointer): 각 노드 안에서, 다음이나 이전의 노드와의 연결 정보를 가지고 있는 공간
* 일반적인 링크드 리스트 형태
파이썬에서 링크드 리스트 구현시 class 사용
class Node:
def __init__ (self, data): # 이 클래스가 객체화 될 때마다
self.data = data
self.next = None
class Node:
def __init__(self, data, next=None): # self는 항상 첫번째 인자로 붙지만 self를 쓰지는 않는다. 실제 인자는 data 하나이다. 만약 다음 노드의 주소를 넣어주려면 두번째 인자에 넣어준다.
self.data = data
self.next = next
간단한 Linked List 구현하기, 노드와 노드 연결하기
node1 = Node(1) # 1이 data 인자값으로 들어가고, 주소값은 None이 들어간다.
node2 = Node(2) # 객체를 2개 만들었지만 아직 연결은 안돼있다.
node1.next = node2 # node1의 주소가 node2를 가리킨다.
head = node1 # 노드1의 주소 값데이터 축적하기
class Node:
def __init__ (self, data, next = None):
self.data = data
self.next = next
def add(data):
node = head # 노드는 헤드의 값을 가져온다.
while node.next: # 맨 끝의 데이터를 찾아가기 위해서 node.next 가 있는지 보고 = 다음 주소가 저장되어 있는지 보고
node = node.next # 노드 찾기
node.next = Node(data) # node.next가 None이면, 현재 객체의 next가 비어있으므로 새로운 주소를 next로 가리켜 준다.
node1 = Node(1) # 연결리스트의 첫 노드 만들기
head = node1 # 첫 노드의 주소를 head에 저장
for index in range(2, 10):
add(index)
Linked List 데이터 출력하기(검색하기)
node = head
while node.next:
print(node.data)
node = node.next # 노드가 다음 노드를 가리키게 해주기
print(node.data) # 마지막 노드의 데이터
1
2
3
4
5
6
7
8
9Linked List의 장단점 (전통적인 C언어에서의 배열과 Linked List)
장점
- 미리 데이터 공간을 미리 할당하지 않아도 됨
- 배열은 미리 데이터 공간을 할당 해야 함
단점
- 연결을 위한 별도 데이터 공간이 필요하므로, 저장공간 효율이 높지 않음
- 연결 정보를 찾는 시간이 필요하므로 접근 속도가 느림
- 중간 데이터 삭제시, 앞뒤 데이터의 연결을 재구성해야 하는 부가적인 작업 필요
Linked List의 복잡한 기능1 (Linked List 데이터 사이에 데이터를 추가)
- 링크드 리스트는 유지 관리에 부가적인 구현이 필요함
node3 = Node(1.5)
node = head # 맨앞의 노드는 헤드
search = True
while search: # search가 계속 true이면 계속 노드를 봐보자
if node.data == 1: # 현재 노드가 1이 될때까지 계속 본다.
search = False # 노드가 1이라면 while문이 끝난다.
else :
node = node.next # 노드가 1이 아니라면 계속 다음 노드 보기
node_next = node.next # 원래 있었던 다음 노드의 주소를 node_next라는 변수에 저장
node.next = node3 # node3의 주소를 node.next로 변경
node3.next = node_next # 원래 있었던 다음 노드의 주소를 node3.next에 저장
파이썬 객체지향 프로그래밍으로 Linked List 만들기
class Node:
def __init__(self, data, next=None):
self.data = data
self.next = next
class NodeMgnt:
def __init__(self, data):
self.head = Node(data) # 맨앞의 노드 값
def add(self, data): # 무조건 맨 뒤에 넣는다.
if self.head == "" :
self.head = Node(data)
else :
node = self.head
while node.next: # node.next가 None이지 않으면
node = node.next # node.next는 다음 주소를 가리킨다.
node.next = Node(data) # 그 노드는 마지막 노드가 된다. 주소 연결
def desc(self):
node = self.head
while node:
print(node.data)
node = node.next
linkedlist1 = NodeMgmt(0) # 0을 가진 객체 만들기
linkedlist1.desc() # 노드의 헤드값부터 시작해서 순차적으로 순회하며 노드값 가져온다.
for data in range(1, 10):
linkedlist1.add(data)
linkedlist1.desc()
0
1
2
3
4
5
6
7
8
9
Linked List의 복잡한 기능2 (특정 노드를 삭제)
- 다음 코드는 위의 코드에서 delete 메서드만 추가한 것이므로 해당 메서드만 확인하면 됨
- head 삭제
- 마지막 노드 삭제
- 중간 노드 삭제
def delete(self, data):
if self.head == "":
print("해당 값을 가진 데이터가 없습니다.")
return
# 1. head 삭제
if self.head.data == data:
temp = self.head
self.head = self.head.next
del temp
else:
node = self.head # 해당 노드의 주소값
while node.next: # node.next 가 존재한다면, 다음으로 볼게 있다면
if node.next.data == data: # 다음 노드의 데이터가 삭제할 데이터라면
temp = node.next # temp에 저장해주고
node.next = node.next.next
del temp
테스트를 위해 1개 노드를 만들어 봄
linkedlist1 = NodeMgmt(0)
linkedlist1.desc()
0
head 가 살아있음을 확인
linkedlist1.head
<__main__.Node at 0x1099fc6a0>
head 를 지워봄(위에서 언급한 경우의 수1)
linkedlist1.delete(0)
다음 코드 실행시 아무것도 안나온다는 것은 linkedlist1.head 가 정상적으로 삭제되었음을 의미
linkedlist1.head
다시 하나의 노드를 만들어봄
linkedlist1 = NodeMgmt(0)
linkedlist1.desc()
0
이번엔 여러 노드를 더 추가해봄
for data in range(1, 10):
linkedlist1.add(data)
linkedlist1.desc()
0
1
2
3
4
5
6
7
8
9
노드 중에 한개를 삭제함 (위에서 언급한 경우의 수2)
linkedlist1.delete(4)특정 노드가 삭제되었음을 알 수 있음
linkedlist1.desc()
0
1
2
3
5
6
7
8
9
데이터가 특정 숫자인 노드 찾는 함수 만들기
class Node:
def __init__(self, data):
self.data = data
self.next = None
class NodeMgmt:
def __init__(self, data):
self.head = Node(data)
def add(self, data):
if self.head == '':
self.head = Node(data)
else:
node = self.head
while node.next:
node = node.next
node.next = Node(data)
def desc(self):
node = self.head
while node:
print (node.data)
node = node.next
def delete(self, data):
if self.head == '':
print ('해당 값을 가진 노드가 없습니다.')
return
if self.head.data == data: # 경우의 수1: self.head를 삭제해야할 경우 - self.head를 바꿔줘야 함
temp = self.head # self.head 객체를 삭제하기 위해, 임시로 temp에 담아서 객체를 삭제했음
self.head = self.head.next # 만약 self.head 객체를 삭제하면, 이 코드가 실행이 안되기 때문!
del temp
else:
node = self.head
while node.next: # 경우의 수2: self.head가 아닌 노드를 삭제해야할 경우
if node.next.data == data:
temp = node.next
node.next = node.next.next
del temp
pass
else:
node = node.next
def search_node(self, data):
node = self.head
while node:
if node.data == data:
return node
else:
node = node.next
Double Linked List 구조
더블 링크드 리스트(Double linked list) 기본 구조
- 이중 연결 리스트라고도 함
- 장점: 양방향으로 연결되어 있어서 노드 탐색이 양쪽으로 모두 가능
class Node:
def __init__ (self, data, prev=None, next=None):
self.prev = prev
self.next = next
self.data = data
class NodeMgnt:
def __init__ (self,data):
self.head = Node(data) # 데이터의 주소값을 현재 노드의 헤드값으로
self.tail = self.head #
def insert(self, data): # 맨뒤에 데이터를 넣는다.
if self.head == None: # 헤드가 비어있으면
self.head == Node(data) # 헤드를 만들면 된다.
self.tail == self.head # 꼬리도 만들면 된다.
else : # 헤드가 존재 한다면, 노드가 존재한다면, 계속 쫒아가야한다.
node = self.head # 헤드를 특정 변수에 넣어놓고
while node.next: # node의 맨 끝이 None이라면 끝난다. 고로 끝까지 계속 본다는 것
node = node.next # 노드의 끝을 찾아간다.
new = Node(data) # 노드의 끝을 찾아가면 마지막 노드의 주소를 가지고 있을 것이다. 새로운 노드를 만들어 준다.
node.next = new # 새로운 노드를 가리키게끔, 새로운 노드의 주소를 그 전 노드의 꼬리에 넣어준다.
new.prev = node # 그 전 노드의 주소를 새로운 노드의 헤드에 저장해준다.
self.tail = new # 새로운 노드의 주소를 그 전 노드의 꼬리에 저장해준다.
def desc(self):
node = self.head
while node:
print(node.data)
node = node.next
double_linked_list = NodeMgmt(0)
for data in range(1, 10):
double_linked_list.insert(data)
double_linked_list.desc()
0
1
2
3
4
5
6
7
8
9
위 코드에서 노드 데이터가 특정 숫자인 노드 앞에 데이터를 추가하는 함수를 만들고, 테스트해보기
- 더블 링크드 리스트의 tail 에서부터 뒤로 이동하며, 특정 숫자인 노드를 찾는 방식으로 함수를 구현하기
- 테스트: 임의로 0 ~ 9까지 데이터를 링크드 리스트에 넣어보고, 데이터 값이 2인 노드 앞에 1.5 데이터 값을 가진 노드를 추가해보기
class Node:
def __init__(self, data, prev=None, next=None):
self.prev = prev
self.data = data
self.next = next
class NodeMgmt:
def __init__(self, data):
self.head = Node(data)
self.tail = self.head
def insert(self, data):
if self.head == None:
self.head = Node(data)
self.tail = self.head
else:
node = self.head
while node.next:
node = node.next
new = Node(data)
node.next = new
new.prev = node
self.tail = new
def desc(self):
node = self.head
while node:
print (node.data)
node = node.next
def search_from_head(self, data):
if self.head == None:
return False
node = self.head
while node:
if node.data == data:
return node
else:
node = node.next
return False
def search_from_tail(self, data):
if self.head == None:
return False
node = self.tail
while node:
if node.data == data:
return node
else:
node = node.prev
return False
def insert_before(self, data, before_data):
if self.head == None:
self.head = Node(data)
return True
else:
node = self.tail
while node.data != before_data:
node = node.prev
if node == None:
return False
new = Node(data)
before_new = node.prev
before_new.next = new
new.prev = before_new
new.next = node
node.prev = new
return True'🕶 Algorithm > 자료구조' 카테고리의 다른 글
| 공간복잡도 (0) | 2021.07.22 |
|---|---|
| 트리 (0) | 2021.07.20 |
| 해쉬 테이블 (0) | 2021.07.19 |
| 시간복잡도 (0) | 2021.07.16 |
| 자료구조, 알고리즘, 배열, 스택, 큐 (0) | 2021.07.15 |