링크드 리스트
링크드 리스트 구조
- 연결 리스트라고도 함
- 배열은 순차적으로 연결된 공간에 데이터를 나열하는 데이터 구조
- 링크드리스트는 떨어진곳에 존재하는 데이터를 화살표로 연결해서 관리하는 데이터 구조
- 본래 C언어에서는 주요한 데이터 구조이지만, 파이썬은 리스트 타입이 링크드 리스트의 기능을 모두 지원한다.
배열은 연결된 공간을 미리 예약해야한다는 단점이있다. 하지만 링크드 리스트는 미리 예약하지 않고 필요할 때마다 추가할 수 있다.
- 노드 (Node) : 데이터 저장 단위( 데이터 값, 포인터 ) 로 구성
- 포인터( pointer ) : 각 노드 안에서, 다음이나 이전의 노드와의 연결 정보를 가지고 있는 공간
[데이터 | 다음데이터주소 ] → [데이터 | 다음데이터주소] → [데이터 | 다음데이터주소]
다음 데이터 주소를 가리키고 있기 때문에 떨어져 있는 위치에 있어도 다음 노드와 연결할 수 있다. 그리고 마지막노드의 다음 데이터주소값이 비어있으면(null) 데이터의 끝을 알 수 있다.
그리고 새로운 공간을 만들고 이전 노드와 연결시키면 데이터 추가도 용이하다.
링크드 리스트의 구현
class Node:
def __init__(self, data):
self.data = data
self.next = None노드는 데이터와 다음데이터의주소를 갖고있는 구조이기 때문에 class로 구현이 가능하다.
class Node:
def __init__(self, data, next=None):
self.data = data
self.next = next두 가지 방식의 차이점은 인자로 next의 default 값을 주냐 마냐의 차이다.
node1 = Node(1)
node2 = Node(2)
node1.next = node2그리고 node1과 node2를 생성하고. node1.next의 값을 node2로 설정하면 node1이 node2를 가리키는 형태가 될 것이다.
head = node1그리고 head라는 변수를 사용해서 node1이 가장 앞쪽 노드임을 나타낸다.
노드에 새로운 데이터를 추가
class Node:
def __init__(self, data, next=None):
self.data = data
self.next = next
def add(data):
node = head
while node.next:
node = node.next
node.next = Node(data)
node1 = Node(1)
head = node1노드를 클래스를 통해 구현하고 add 함수를 구현한다.
add는 데이터를 받아서 노드의 제일 마지막에 추가한다.
그렇게 하기 위해서는 node를 탐방하고 다음 노드의 주소가 없는 노드를 찾으면 된다.
우선 node라는 변수에 가장 아랫줄에 있는 head를 복사한다.
head는 처음 시작노드임.
그리고 while문을 통해 node.next가 없을 때 까지 반복하며 node에는 다음노드를 넣는다. 그렇게 하다보면 마지막 노드에서 node.next가 null인 노드를 찾을 것이고 그때 while문을 종료하며 node.next에 새로운 노드를 추가하여 생성해준다.
for index in range(2,10):
add(index)
node = head
while node.next:
print(node.data)
node = node.next
print(node.data)확인을 위해 2~9까지의 노드를 추가로 add함수를 사용해서 생성해보고 출력해본다.
링크드리스트 장점
- 미리 데이터 공간을 할당하지 않아도 된다.
- → 배열은 미리 데이터 공간을 할당 해야 함.
링크드리스트 단점
- 연결을 위한 별도의 데이터 공간이 필요하다. 저장공간 효율이 높지 않음
- 연결 정보를 찾는 시간이 필요하므로 접근 속도가 느리다
- 중간 데이터 삭제시, 앞 뒤 데이터와 연결을 재구성해야 하는 부가 적인 작업이 필요하다.
구현
이전 예제에 이어서
node3 = Node(1.5)node3 를 생성해서 1과 2의 사이에 연결해주자.
이를 위해서 1을 찾아서 1의 데이터를 가진 노드의 다음노드주소를 node3으로 바꾸고, 노드3의 다음노드 주소를 노드 2로 바꾸는 과정을 거쳐야한다.
node = head
search = True
while search:
if node.data == 1:
search = False
else:
node = node.next
temp_node = node.next
node.next = node3
node3.next = temp_node
print(temp_node.data)우선 1을 찾는 작업을 while문으로 수행한다. 그리고 새로운 변수를 하나 생성해서 임시로 node.next를 담아두고 node.next를 node3 으로 변경
그리고 node3.next를 임시로 저장해둔 변수로 다시 바꿔주면 된다.
node = head
while node.next:
print(node.data)
node = node.next
print(node.data)이를 다시 출력해보면 node 사이에 값이 추가된 것을 볼 수 있다.
파이썬 객체지향 프로그래밍으로 링크드리스트 구현하기
class Node:
def __init__(self, data, next=None):
self.data = data
self.next = next
class NodeMgmt:
def __init__(self, data):
self.head = Node(data) # 맨 앞의 노드인 head값을 알고 있어야 추가나 검색이 가능하다.
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이번에는 클래스로 링크드리스트를 만들고 추가하고 순회하여 출력하는 프로그램을 구현한다.
NodeMgmt 라는 클래스를 통해 add 와 순회출력을 하고NodeMgmt의 인스턴스 생성과 동시에 해당 노드를 이 링크드리스트의 head로 저장한다.
그리고 혹시나 head가 없이 add를 할 것에 대비하여 if문을 사용한다.
나머지 작업들은 앞서 작업과 같다.
linkedlist1 = NodeMgmt(0)
linkedlist1.desc()
for data in range(1,10):
linkedlist1.add(data)
linkedlist1.desc()linkedlist1 이라는 인스턴스를 만들고 출력해보면 0이라는 값이 잘 들어가고 추가 잘 되는 것을 확인
특정 노드 삭제
[A | B] - [B | C] - [C | null ]
이런 형태의 링크드리스트 에서 특정 노드를 삭제하는 방법은 여러가지가 있다.
A노드를 지우기 위해서는 그냥 A를 삭제하면된다.
하지만 B노드를 삭제하기 위해서는 A노드의 다음노드 주소를 C로 바꿔줘야한다.
그리고 마지막으로 C노드를 삭제하기 위해서는 C노드를 삭제하고 B노드의 다음노드주소를 null로 변경해야한다.
이렇게 특정 노드 삭제는
- head 삭제
- 마지막 노드 삭제
- 중간 노드 삭제
3가지 경우가 있다.
아까 코드에 delete 함수를 추가해보자
class Node:
def __init__(self, data, next=None):
self.data = data
self.next = next
class NodeMgmt:
def __init__(self, data):
self.head = Node(data) # 맨 앞의 노드인 head값을 알고 있어야 추가나 검색이 가능하다.
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: # head 삭제
temp = self.head
self.head = self.head.next
del temp
else :
node = self.head
while node.next:
if node.next.data == data: # 만약 해당 노드의 다음노드가 우리가 삭제할 data라면?
temp = node.next
node.next = node.next.next # 현재 노드의 next를 다음 node의 next를 가리키게 하고
del temp # node.next 삭제
return
else:
node = node.next처음으로 if문에서 self.head.data가 현재 찾는 data라면 self.head를 잠시 temp에 담아두고 self.head를 다음노드의 주소로 바꿔버린다. 그리고 temp를 삭제.
이것이 head 노드를 삭제하는 방법이다.
그리고 중간노드와 마지막노드를 삭제하는 방법은 하나의 방법으로 가능한데.
node에 self.head를 담아두고 순회하다가 node.next의 data가 현재 찾는 데이터라면
node.next를 temp에 담고
현재 노드의 next를 다음노드의 next를 가리키게한다.
그리고 temp를 삭제하면 자연스럽게 중간노드를 삭제할 수 있다.
마지막 노드도 이 코드에 의해 삭제되게 되는데
현재노드에서 다음노드의 next를 가리키게 할때 마지막노드의 next는 None (null) 이기 때문에 해결된다.
다양한 링크드리스트 구조
링크드리스트에서 어떤 데이터를 찾을때는 Head에서 시작해서 찾아나가야 한다. 하지만 노드가 10000 개 정도라고 하고 찾고자하는 데이터가 끝에 위치해있다면 많은 시간이 걸릴 것이다.
그래서 뒤에서 찾기 시작할 수 있다면 뒷쪽에 있는 노드를 조금더 빨리 찾을 수 있다. 이를 보완한 것이 더블 링크드 리스트이다.
더블 링크드 리스트
[이전데이터주소 | 데이터 | 다음데이터 주소 ] ↔ [이전데이터주소 | 데이터 | 다음데이터 주소 ]
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 = Node(data)
def insert(self, data):
if self.head == None:
self.head = Node(data)
self.tail = Node(data)
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.next:
print(node.data)
node = node.next더블링크드리스트의 Node 클래스에는
data와 이전주소를 나타내는 prev, next 변수가 있다.
그리고 NodeMgmt 에는 head와 끝에서 찾기위한 tail을 저장한다.
어차피 초기값은 head이자 tail이기 때문에 같은 값을 가진다.
이후에는 마찬가지로 insert를 위해 tail노드를 찾고 마지막노드의 next에 새 노드 새노드의 prev에 마지막노드를 넣어준다. 그리고 마지막으로 self.tail을 새로 추가한 노드로 변경
이번에는 데이터를 원하는 노드 앞에 추가하는 함수를 작성해보자
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 = Node(data)
def insert(self, data):
if self.head == None:
self.head = Node(data)
self.tail = Node(data)
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.next:
print(node.data)
node = node.next
def search(self,data):
node = self.head#tail
while node:
if node.data == data:
return node
else:
node = node.next#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.next = node
new.prev = before_new
node.prev = newsearch 함수는 그냥 데이터를 찾는 함수이다. 처음부터 끝까지 순회하며 node.data가 내가 찾는 data인지 확인하기만 하면된다.
insert_before은 data와 bofore_data 값을 받아 before_data를 찾으면 앞에 data를 추가해주는 방법이다.
node = self.tail 이나 self.head로 데이터가 어디쪽에 더 가까운지 알 때 유용하다.
while문으로 node.data 와 before_data 가 같을때 까지 반복하며 tail에서 시작했으니 하나씩 prev 로 이동한다. 그리고 만약 node 가 None이 되었다면 결국 못찾았다는 뜻이므로 그냥 False를 반환한다.
만약 찾았다면 while문을 빠져나와
new 에 새로운 노드를 생성하고
bofore_new라는 변수를 새로 만들어 node.prev를 저장해둔다.
그리고 before_new의 next를 새로 만든 new로 지정.
new.next는 당연히 내가 찾던 노드를 가리키고 new.prev는 아까 before_new에 담아두었던 노드를 가리킨다.
여기서 끝이아니라 현재 노드의 prev를 새 노드 new로 바꿔주기만 하면된다.
linked1 = NodeMgmt(0)
for i in range(1,10):
linked1.insert(i)
node3 = linked1.search(3)
if node3:
print(node3.data)
else:
print("no data")
linked1.insert_before(1.5,2)
linked1.desc()실행 결과 확인해보기~
'python' 카테고리의 다른 글
| 네카라쿠배 프론트엔드 취업완성 스쿨 2기 2차 테스트 6일차 학습 (0) | 2021.06.22 |
|---|---|
| 네카라쿠배 프론트엔드 취업완성 스쿨 2기 2차 테스트 5일차 학습 (0) | 2021.06.19 |
| 네카라쿠배 프론트엔드 취업완성 스쿨 2기 2차 테스트 4일차 학습 (0) | 2021.06.17 |
| 네카라쿠배 프론트엔드 취업완성 스쿨 2기 2차 테스트 3일차 학습 (0) | 2021.06.16 |
| 네카라쿠배 프론트엔드 취업완성 스쿨 2기 2차 테스트 2일차 학습 (0) | 2021.06.15 |
댓글