[알고리즘 포스팅 순서]
1. 시간복잡도
2. 배열
3. 연결리스트
4. 스택
5. 큐
6. 트리
7. 그래프
8. 해쉬테이블
9. 정렬(선택, 버블, 삽입, 퀵, 힙, 병합)
10. 코테 대비 백준 문제 풀이 꿀팁
오늘 알아볼 자료구조는 연결리스트이다.
[연결리스트란?]
연결 리스트는 사슬처럼 여러 데이터를 연결한 것이다.
연결 리스트는 배열처럼 선형 자료 구조이지만, 연속한 메모리에 값을 저장하는 것은 아니다.
연결 리스트에서는 각각의 데이터(원소)들을 노드라고 부른다.
[특징]
1. 종류로는 단일 연결 리스트(Singly Linked List), 이중 연결 리스트(Doubly linked list), 순환 이중 연결 리스트(Circular Doubly linked list)가 존재한다.
단일 연결 리스트는 한 방향으로만 연결 및 이동이 가능한 리스트이고
이중 연결 리스트는 양방향으로 연결 및 이동이 가능한 리스트이고
순환 이중 연결 리스트는 이중 연결 리스트에서 머리와 꼬리가 연결되어 있는 리스트이다.
2. 머리 노드와 꼬리 노드
연결 리스트는 리스트와 다르게 머리 노드와 꼬리 노드가 있다.
머리 노드는 시작 노드를, 꼬리 노드는 마지막 노드를 의미하며
이 두 노드엔 데이터가 따로 담기지 않고 다음 연결되는 노드의 주소를 참조한다.
3. 연결
그렇다면 어떻게 연결하겠다는 것일까?
단일 연결 리스트의 경우에는 self.data와 self.next라는 변수를 이용하여
이중 연결 리스트는 위에서 self.prev라는 변수를 추가해서 사용한다.
더 자세히 알아보기 위해 코드를 살펴보자
[코드]
(1) 단일 연결 리스트: 코드로 다음과 같은 기능을 지원하도록 구현하였다.
- push_back(Data data): 연결 리스트의 tail에 data를 삽입
- push_front(Data data): 연결 리스트의 head에 data를 삽입
- insert(Iterator it, Data data): it위치에 data를 삽입
- insert(Iterator it, Data data[]): it위치에 data들을 삽입
- front(), back(): 각각은 연결리스트의 head의 값과 tail의 값을 리턴
- delete(Iterator it): it 위치의 데이터를 삭제
- delete(Iterator it, Number count): it 위치의 데이터를 count개만큼 삭제
- size(): 연결리스트에 존재하는 모든 노드의 수 반환
from multipledispatch import dispatch #오버로딩이 안되는 파이썬에 가능하게 만듦
class Node:
def __init__(self, data):
self.data = data
self.next = None
class Single_Linked_List:
def __init__(self):
self.head = None
self.size = 0
def push_back(self, data): # 연결 리스트의 tail에 data 삽입
node = Node(data)
if self.head is None:
self.head = node
else:
prev = self.head
while prev.next:
prev = prev.next
prev.next = node
self.size += 1
def push_front(self, data): # 연결 리스트의 head에 data 삽입
node = Node(data)
if self.head is None:
self.head = node
else:
node.next = self.head
self.head = node
self.size += 1
def insert(self, it, data): # it 위치에 data 삽입
if (it <= 0):
self.push_front(data)
elif (0 < it < self.size):
prev = self.head
for i in range(it-1):
prev = prev.next
node = Node(data)
node.next = prev.next
prev.next = node
self.size += 1
else:
print("인덱스 값이 범위를 벗어났습니다.")
def insert(self, it, *data): # it 위치들에 data들 삽입 # *은 여러개의 인자값을 받을 수 있도록함
for i in range(len(data)):
if (it <= 0):
self.push_front(data[i])
elif (0 < it < self.size):
prev = self.head
for i in range(it-1):
prev = prev.next
node = Node(data[i])
node.next = prev.next
prev.next = node
self.size += 1
else:
print("인덱스 값이 범위를 벗어났습니다.")
@dispatch(int)
def delete(self, it):# it 위치의 data 삭제
if (it == 0):
self.head = self.head.next
self.size -= 1
elif ( 1 <= it < self.size):
prev = self.head
for i in range(it-1):
prev = prev.next
prev.next = prev.next.next
self.size -= 1
else:
print("인덱스 값이 범위를 벗어났습니다.")
@dispatch(int, int)
def delete(self, it, count): # it 위치부터 data들 count갯수만큼 삭제
for i in range(count):
if (it == 0):
self.head = self.head.next
self.size -= 1
elif ( 1 <= it < self.size):
prev = self.head
for i in range(it-1):
prev = prev.next
prev.next = prev.next.next
self.size -= 1
else:
print("인덱스 값이 범위를 벗어났습니다.")
def front(self): # head값 리턴
return print("head:", self.head.data)
def back(self): # tail값 리턴
tail = self.head
for i in range(self.size-1):
tail = tail.next
return print("tail:", tail.data)
def get_size(self): # 연결된 size 리턴
return print("size: ", self.size)
## __main__ ##
linklist = Single_Linked_List()
linklist.push_back(3) #추가
linklist.push_front(1) #추가
linklist.get_size() #2
linklist.insert(1, 2) #추가
linklist.push_front(0) #추가
linklist.push_back(7) #추가
linklist.front()
linklist.back()
linklist.get_size() #5
linklist.delete(2) #삭제
linklist.delete(0, 2) #삭제
linklist.front()
linklist.back()
linklist.get_size() #2
linklist.insert(0, 1, 2, 3, 4, 5, 6) #추가*6
linklist.front()
linklist.back()
linklist.get_size() #8
-> main문을 실행하면 다음과 같은 결과가 나온다.
(2) 이중 연결 리스트: 위와 동일한 기능을 지원하도록 구현하였다.
- push_back(Data data): 연결 리스트의 tail에 data를 삽입합니다.
- push_front(Data data): 연결 리스트의 head에 data를 삽입합니다.
- insert(Iterator it, Data data): it위치에 data를 삽입합니다.
- insert(Iterator it, Data data[]): it위치에 data들을 삽입합니다.
- front(), back(): 각각은 연결리스트의 head의 값과, tail의 값을 리턴합니다.
- delete(Iterator it): it 위치의 데이터를 삭제합니다.
- delete(Iterator it, Number count): it 위치의 데이터를 count개만큼 삭제합니다.
- size(): 연결리스트에 존재하는 모든 노드의 수를 구합니다.
from multipledispatch import dispatch #오버로딩이 안되는 파이썬에 가능하게 만듦
class Node(object):
def __init__(self, data, prev = None, next = None):
self.data = data
self.prev = prev
self.next = next
class Double_Linked_List2(object):
def __init__(self):
self.head = Node(None)
self.tail = Node(None, self.head)
self.head.next = self.tail
self.size = 0
def selectNode(self, idx): # idx에 따른 노드 찾기
if idx > self.size:
print("인덱스 값이 범위를 벗어났습니다.")
return None
if idx == 0:
return self.head
if idx == self.size:
return self.tail
if idx <= self.size//2:
target = self.head
for _ in range(idx):
target = target.next
return target
else:
target = self.tail
for _ in range(self.size - idx):
target = target.prev
return target
def push_back(self, data): # tail에 노드 추가
if self.size == 0:
self.head = Node(data)
self.tail = Node(None, self.head)
self.head.next = self.tail
else:
tmp = self.tail.prev
newNode = Node(data, tmp, self.tail)
tmp.next = newNode
self.tail.prev = newNode
self.size += 1
def push_front(self, data): # head에 노드 추가
if self.size == 0:
self.head = Node(data)
self.tail = Node(None, self.head)
self.head.next = self.tail
else:
tmp = self.head
self.head = Node(data, None, self.head)
tmp.prev = self.head
self.size += 1
def insert(self, idx, data): # idx에 노드 추가
if self.size == 0:
self.head = Node(data)
self.tail = Node(None, self.head)
self.head.next = self.tail
else:
tmp = self.selectNode(idx)
if tmp == None:
return
if tmp == self.head:
self.push_front(data)
elif tmp == self.tail:
self.push_back(data)
else:
tmp_prev = tmp.prev
newNode = Node(data, tmp_prev, tmp)
tmp_prev.next = newNode
tmp.prev = newNode
self.size += 1
def insert(self, idx, *data): # idx에 노드들 추가
for i in range(len(data)):
if self.size == 0:
self.head = Node(data[i])
self.tail = Node(None, self.head)
self.head.next = self.tail
else:
tmp = self.selectNode(idx)
if tmp == None:
return
if tmp == self.head:
self.push_front(data[i])
elif tmp == self.tail:
self.push_back(data[i])
else:
tmp_prev = tmp.prev
newNode = Node(data[i], tmp_prev, tmp)
tmp_prev.next = newNode
tmp.prev = newNode
self.size += 1
@dispatch(int)
def delete(self, idx): # idx의 노드 삭제
if self.size == 0:
print("더이상 삭제할 노드가 없습니다")
return
else:
tmp = self.selectNode(idx)
if tmp == None:
return
elif tmp == self.head:
tmp = self.head
self.head = self.head.next
elif tmp == self.tail:
tmp = self.tail
self.tail = self.tail.prev
else:
tmp.prev.next = tmp.next
tmp.next.prev = tmp.prev
del(tmp)
self.size -= 1
@dispatch(int, int)
def delete(self, idx, count): # idx의 노드 삭제
for i in range(count):
if self.size == 0:
print("더이상 삭제할 노드가 없습니다.")
return
else:
tmp = self.selectNode(idx)
if tmp == None:
return
elif tmp == self.head:
tmp = self.head
self.head = self.head.next
elif tmp == self.tail:
tmp = self.tail
self.tail = self.tail.prev
else:
tmp.prev.next = tmp.next
tmp.next.prev = tmp.prev
del(tmp)
self.size -= 1
def front(self): # head값 리턴
return print("head:", self.head.data)
def back(self): # tail값 리턴
return print("tail:", self.tail.prev.data)
def get_size(self): # size값 리턴
return print("size: ", self.size)
def printlist(self): # 전체 list 프린트
target = self.head
while target != self.tail:
if target.next != self.tail:
print(target.data, '<=> ', end='')
else:
print(target.data)
target = target.next
## __main__ ##
mylist = Double_Linked_List2()
mylist.push_back('A')
mylist.printlist()
mylist.push_back('B')
mylist.printlist()
mylist.push_back('C')
mylist.printlist()
mylist.insert(1, 'D')
mylist.printlist()
mylist.push_front('E')
mylist.printlist()
mylist.get_size()
mylist.delete(0)
mylist.printlist()
mylist.delete(3)
mylist.printlist()
mylist.delete(0)
mylist.printlist()
mylist.insert(1, 'a', 'b', 'c')
mylist.printlist()
mylist.front()
mylist.back()
mylist.get_size()
-> main문을 실행하면 다음과 같은 결과가 나온다.
끄읏
[참고문헌]
1. 위키독스: https://wikidocs.net/224937
2. 블로그(연결 리스트 이론): https://byumm315.tistory.com/entry/%EB%A6%AC%ED%8A%B8%EC%BD%94%EB%93%9C-23-Merge-k-Sorted-Lists
3. 블로그(이중 연결 리스트 코드): https://underflow101.tistory.com/4
4. 동영상(이론, 강추): https://www.youtube.com/watch?v=DzGnME1jIwY&list=PLjSkJdbr_gFZQp0KEoo0Y4KkCI5YqxtjZ&index=2
5. 사진출처: http://wiki.hash.kr/index.php?title=%EC%97%B0%EA%B2%B0%EB%A6%AC%EC%8A%A4%ED%8A%B8&mobileaction=toggle_view_desktop, https://underflow101.tistory.com/4, https://bigbigpark.github.io/data_structure/linkedlist/
'IT > 알고리즘' 카테고리의 다른 글
[알고리즘(6)] Python으로 알아보는 트리(Tree) (0) | 2024.03.31 |
---|---|
[알고리즘(5)] Python으로 알아보는 큐(Queue) (2) | 2024.03.16 |
[알고리즘(4)] Python으로 알아보는 스택(Stack) (0) | 2024.03.15 |
[알고리즘(2)] Python으로 알아보는 배열(Array) (2) | 2024.03.13 |
[알고리즘(1)] 시간복잡도/공간복잡도 (2) | 2024.03.08 |