핵심 자료구조 기본인 단일 연결리스트(linked list) 개념파악하기
1. 연결리스트(linked list)
배열의 시간복잡도는 삽입과 삭제가 O(N)이다.
삽입과 삭제가 자주 일어나는 상황에 배열에 들어있는 원소의 수가 매우 많다면 단순한 배열은 비효율적이다.
이런 문제를 해결하기 위해 등장한 자료구조가 연결리스트(linked list)
연결리스트는 탐색은 느리지만(O(N)) 삽입과 삭제 연산이 매우 빠르다(O(1))
따라서 삽입과 삭제가 잦은 경우에 연결리스트를 이용하면 효과적으로 문제를 해결할 수 있다.
2. 노드(node)
노드는 데이터를 담는 곳이다.
연결리스트는 여러개의 노드들의 모임이다.
연결리스트에서 하나의 노드는 데이터와 다른 노드로 이동하는 경로를 갖는다.
노드를 정의하는 방법에 따라 앞 뒤로 이동할 수 있다.
3. 단일 연결리스트
단일 연결리스트는 연결 방향이 단방향인 연결리스트이다.
여기서 각 노드별로 data와 next값을 가지며, data는 값이고, next는 다음 노드의 위치를 가리킨다.
다음과 같이 3을 가지는 노드가 존재한다.
다음 노드는 존재하지 않아서 next에는 기본적으로 null이 들어있다.
이러한 노드를 만드는 것을 python으로 써볼까?
class Node():
def __init__(self,data,next=None):
self.data = data
self.next = next
node1 = Node(3)
"""
node1 = Node()
node1.data = 3
"""
이렇게 만든 노드에 5를 값으로 가지는 새로운 노드 node2를 만든다.
여기서 node1이 node2를 가리키도록 만들고 싶다.
node1.next = node2로 하면 될것이다.
node2 = Node(5)
node1.next = node2
node1.next = node2는 node1의 next가 가리키는 노드가 node2 그 자체
따라서 다음과 같이 출력해보면...
class Node():
def __init__(self,data,next=None):
self.data = data
self.next = next
node1 = Node(3)
node2 = Node(5)
node1.next = node2
print(node2.data)
print(node1.next.data)
5
5
node1과 node2를 다시 분리하고 싶다면.. 그냥 node1.next = None을 넣어주면 된다
class Node():
def __init__(self,data,next=None):
self.data = data
self.next = next
node1 = Node(3)
node2 = Node(5)
node1.next = node2
print(node2.data)
print(node1.next.data)
node1.next = None
print(node1.next.data)
지금까지 단일 연결 리스트를 생성하는 법에 대해 배웠는데..
이렇게하면 문제가 되는 부분은 도대체 시작점이 어디냐 이거다.
3번째부터 시작한다면, 1번째, 2번째는 볼 수 없겠지
따라서 단일 연결리스트의 시작점 Head를 명시해줘야한다.
그리고 연결리스트가 어디까지 연결된건지 Tail도 명시해주면 좋다.
Head부터 Tail까지 탐색은 모든 원소를 일일이 확인하므로 O(N)이라는 시간이 소요되지만, 삽입과 삭제의 경우는
해당 위치에서 연결시키거나(삽입) 연결을 끊거나(삭제) 하기만 하면 되니까 O(1)이다.
(당연히 삽입, 삭제를 어떤 위치에서 해야하는지 모를때.. 그 위치를 찾는데 시간이 소요된다면 O(N)이겠지)
또한 단일연결리스트는 단방향으로만 진행되니까 탐색을 위해 앞으로 진행하면, 뒤로 돌아갈수 없는 구조이다.
뒤쪽 부분을 보고싶다면 처음부터 다시해야한다 이 말이지
4. 연결리스트의 삽입
tail 뒤쪽에 값을 삽입한다고 가정해보자.
tail은 next가 비어있으므로 새로운 노드가 들어온다면 next가 가리키는 노드를 해당 노드로 지정해주면 연결 처리는 큰 문제가 없어질 것이다.
근데 연결을 했다면 이제는 tail은 새로 만든 노드가 tail이 된다
그러므로 tail이 무엇인지 표시하는 부분도 변경해줘야겠다
구현이 조금 이상한것 같은데.. 대충 이런 느낌?
class Node():
def __init__(self,data,next=None):
self.data = data
self.next = next
class SLL():
def __init__(self,head=None, tail=None):
self.head = None
self.tail = None
def insert_end(self,num):
#새로운 노드를 만든다.
new_node = Node(num)
#현재 tail의 next에 새로운 노드를 이어붙인다
SLL.tail.next = new_node
#현재 tail을 변경한다
SLL.tail = new_node
비슷하게 head 앞에 새로운 값을 추가하는 작업도 새로운 노드를 만들고 그 노드의 next를 head에 연결하며
현재 head를 새로 만든 노드로 변경
class Node():
def __init__(self,data,next=None):
self.data = data
self.next = next
class SLL():
def __init__(self,head=None, tail=None):
self.head = None
self.tail = None
def insert_end(self,num):
#새로운 노드를 만든다.
new_node = Node(num)
#현재 tail의 next에 새로운 노드를 이어붙인다
self.tail.next = new_node
#현재 tail을 변경한다
self.tail = new_node
def insert_front(self,num):
#새로운 노드를 만든다
new_node = Node(num)
#새로운 노드의 next를 head에 연결
new_node.next = self.head
#현재 head를 새로운 노드로 변경
self.head = new_node
하지만 head 바로 뒤에 노드를 추가하는 작업은 어떨까?
새로운 노드를 일단 만들고
새로운 노드의 next값을 head의 next에 연결
이제 head의 next값을 새로만든 노드로 변경
class Node():
def __init__(self,data,next=None):
self.data = data
self.next = next
class SLL():
def __init__(self,head=None, tail=None):
self.head = None
self.tail = None
def insert_end(self,num):
#새로운 노드를 만든다.
new_node = Node(num)
#현재 tail의 next에 새로운 노드를 이어붙인다
self.tail.next = new_node
#현재 tail을 변경한다
self.tail = new_node
def insert_front(self,num):
#새로운 노드를 만든다
new_node = Node(num)
#새로운 노드의 next를 head에 연결
new_node.next = self.head
#현재 head를 새로운 노드로 변경
self.head = new_node
def insert_after_head(self,num):
#새로운 노드 만들기
new_node = Node(num)
#새로운 노드의 next를 head의 next에
new_node.next = self.head.next
#현재 head의 next를 새로운 노드에
self.head.next = new_node
5. 연결리스트의 삭제
삽입은 연결을 새로 정의했지만, 삭제는 연결을 제거해야한다.
삭제할 때 유의할 점은 삭제하게 되는 노드의 바로 전 노드에서 next를 그 다음 노드로 바꿔줘야한다는 점
예를 들어 tail을 삭제하는 과정을 생각해보자
중간 파란 노드를 삭제한다면.. head 부분의 next를 tail로 바꿔줘야 한다
head는 어떻게 삭제할까?
head의 값을 head.next로 바꿔주면 끝이다
이러면 실제로 삭제하는 것은 아니더라도 다음과 같이 마치 노드가 삭제된 것처럼 보이게 될 것
class Node():
def __init__(self,data,next=None):
self.data = data
self.next = next
class SLL():
def __init__(self,head=None, tail=None):
self.head = None
self.tail = None
def insert_end(self,num):
#새로운 노드를 만든다.
new_node = Node(num)
#현재 tail의 next에 새로운 노드를 이어붙인다
self.tail.next = new_node
#현재 tail을 변경한다
self.tail = new_node
def insert_front(self,num):
#새로운 노드를 만든다
new_node = Node(num)
#새로운 노드의 next를 head에 연결
new_node.next = self.head
#현재 head를 새로운 노드로 변경
self.head = new_node
def insert_after_head(self,num):
#새로운 노드 만들기
new_node = Node(num)
#새로운 노드의 next를 head의 next에
new_node.next = self.head.next
#현재 head의 next를 새로운 노드에
self.head.next = new_node
def delete_front(self):
#현재 head를 head.next로 변경
self.head = self.head.next
인자로 넘어온 num값과 일치하는 node를 찾아서 해당 노드를 지워주는 delete 함수를 생각해보자.
먼저 head를 찾는다
그리고 넘어온 num을 가지는 node를 탐색하기 시작한다
만약 현재 node의 next가 가지는 data가 num이 아니라면..
다음 node로 이동해도 좋으니까 현재 node를 다음 node인 node.next로 바꿔준다
어찌하다가 다음 노드의 데이터가 num이라면... 즉 node.next.data == num이라면..
반복문을 탈출하고 node.next를 삭제하면 된다
node.next를 삭제할려면?
node.next를 node.next.next로 바꿔주면 된다!
class Node():
def __init__(self,data,next=None):
self.data = data
self.next = next
class SLL():
def __init__(self,head=None, tail=None):
self.head = None
self.tail = None
def insert_end(self,num):
#새로운 노드를 만든다.
new_node = Node(num)
#현재 tail의 next에 새로운 노드를 이어붙인다
self.tail.next = new_node
#현재 tail을 변경한다
self.tail = new_node
def insert_front(self,num):
#새로운 노드를 만든다
new_node = Node(num)
#새로운 노드의 next를 head에 연결
new_node.next = self.head
#현재 head를 새로운 노드로 변경
self.head = new_node
def insert_after_head(self,num):
#새로운 노드 만들기
new_node = Node(num)
#새로운 노드의 next를 head의 next에
new_node.next = self.head.next
#현재 head의 next를 새로운 노드에
self.head.next = new_node
def delete_front(self):
#현재 head를 head.next로 변경
self.head = self.head.next
#인자로 받아온 num을 가지는 노드를 삭제(항상 존재하고, head,tail이 아니다)
def delete(self,num):
node = self.head
while node.next.data != num:
node = node.next
node.next = node.next.next
6. 연결리스트의 탐색
삽입과 삭제에서 head tail을 자꾸 변경해주는 이유는 탐색을 원활하게 하기 위함이다.
단일 연결리스트에서는 시작부터 끝을 확실하게 정해줘야 시작점의 head부터 출발해서 tail이 나오기 전까지, next를 계속 따라가면서 탐색을 진행할 수 있다.
7. 연습문제
오름차순으로 정렬된 두 연결리스트를 하나로 합치고, 합친 결과물도 정렬되도록 만들고 싶다면?
def solution(SLL1, SLL2):
result = SLL()
#두 연결리스트의 head를 가져오고
node1 = SLL1.head
node2 = SLL2.head
while node1 != null or node2 != null:
#node2가 없거나, node1이 존재하고, node1의 데이터가 node2보다 작다면
if node2 == null or (node1 != null and node1.data < node2.data):
#node1의 데이터를 먼저 넣고
result.insert_end(node1.data)
#node1의 head 이동
node1 = node1.next
else: #node2의 데이터가 node1의 데이터보다 작다면..
#node2의 데이터를 넣고
result.insert_end(node2.data)
#node2의 head이동
node2 = node2.next
return result
다음 코드 출력을 나열해보면..?
def solution():
sll = SLL()
sll.insert_front(15)
sll.insert_front(25)
sll.insert_end(20)
sll.insert_front(45)
sll.insert_end(30)
node = sll.head
while node != null
print(node.data)
node = node.next
아무것도 없는 연결리스트에 15를 넣으면..
이 연결리스트 head 앞에 25를 넣어주면...
tail 뒤에 20을 넣어주면..? 25 > 15 > 20
head 앞에 45를 넣어주면..? 45 > 25> 15> 20
tail 뒤에 30을 넣어주면..?
'알고리즘 > Java 기초' 카테고리의 다른 글
| 자바 초보에서 B형까지5 -문자열 필수지식- (0) | 2023.02.26 |
|---|---|
| 자바 자료구조2 -이중 연결리스트(LinkedList) (0) | 2023.02.24 |
| 자바 자료구조1 -동적배열(ArrayList) (0) | 2023.02.23 |
| 자바 초보에서 알고리즘 B형까지 도전기4 -배열 필수지식1- (0) | 2023.02.22 |
| 자바 초보에서 알고리즘 B형까지 도전기3 -반복문 필수지식1- (0) | 2023.02.22 |
