[코드트리] 단일 연결 리스트

노드의 정의

배열의 시간복잡도는 중간 삽입과 삭제의 시간 복잡도가 O(N)이다.

삽입과 삭제를 매우 자주 해야 하는 상황에서 배열은 비효율적이다.

 

이 문제를 해결하기 위해 삽입과 삭제가 잦은 상황에서는 연결 리스트 자료구조를 사용한다.

탐색은 O(N)으로 느리지만 삽입과 삭제 연산은 O(1)로 굉장히 빠르다.

 

연결 리스트에서는 노드라는 개념에 대한 이해가 필요하다.

노드란 '정보를 담는 하나의 창구'라고 이해하면 쉽다.

 

일반적으로 연결 리스트에서 하나의 노드는 데이터와 다른 노드로 이동하는 경로를 갖고 있다.

연결 리스트는 여러개의 노드가 모여서 형성되는 구조라고 생각하면 된다.

 

요약하자면

연결 리스트에서 노드란 정보를 담는 하나의 창구로, 연결 리스트는 노드 간의 연속적인 연결로 구성되어 있다.

정의하는 방법에 따라 앞/뒤로 이동할 수 있다.

 

단일 연결 리스트 - 개념/생성

'단일'연결 리스트는 연결 방향이 단방향이라는 의미이다.

각 노드별로 Data와 Next 값을 가지고 있는데, Data는 값, Next는 다음 노드의 위치를 의미한다.

Next 값에 별다른 값을 지정하지 않으면 기본으로 Null이 들어간다.

 

 

data가 없는 상태로 만든 뒤 해당 노드에 값을 넣어주는 식으로 표현하면

set node1 = node(3)

set node1 = node()
node1.data = 3

 

이 노드 바로 뒤에 값이 5인 노드를 추가해 연결한다. 이름은 node2이다.

set node2 = node(5)
node1.next = node2

 

따라서 다음 코드를 실행하면 node2의 값이 출력된다.

set node1 = node(3)
set node2 = node(5)
node1.next = node2


print(node2.data)         # 5
print(node1.next.data)    # 5

 

연결된 노드를 다시 분리하고 싶다면 node1.next에 다시 null을 넣어주면 된다.

set node1 = node(3)
set node2 = node(5)
node1.next = node2

print(node1.next.data)    # 5 
node1.next = null         # 두 관계를 끊어줍니다.

 

이렇게 next 값에 null을 넣어주는 것은 노드를 삭제할 때 이용한다.

 

리스트의 모든 값을 탐색할 때는 시작점을 반드시 명시해야 한다. 이것을 head라고 한다.

종료되는 지점도 명시해 두면 탐색할 때 추가적인 처리 없이 방문 가능한 노드가 종료 지점인지 판단하는 과정만 거쳐서 탐색을 종료할 수 있다.

 

단일연결리슽의 삽입, 삭제는 O(1), 탐색은 O(N)이다.

단방향으로만 진행되므로 뒤로 돌아갈 수 없는 구조임을 유의하자.

 

 

단일 연결 리스트 - 삽입/삭제/탐색

삽입

tail 뒤쪽에 값을 삽입하는 경우

function SLL.insert_end(num)
  set new_node = node(num)       # Step 1. 노드 만들기
  SLL.tail.next = new_node       # Step 2. 이어 붙이기
  SLL.tail = new_node            # Step 3. Tail 변경하기

 

head 앞에 새로운 값을 삽입하는 경우

function SLL.insert_front(num)
  set new_node = node(num)       # Step 1. 노드 만들기
  new_node.next = SLL.head       # Step 2. 이어 붙이기
  SLL.head = new_node            # Step 3. Head 변경하기

 

head 뒤에새로운 값을 삽입하는 경우

function SLL.insert_after_head(num)
  set new_node = node(num)            # Step 1. 노드 만들기
  new_node.next = SLL.head.next       # Step 2. 새로운 노드의 next 값 변경
  SLL.head.next = new_node            # Step 3. Head의 next 값 변경

 

삭제

삽입은 연결을 새로 정의하지만 삭제는 연결을 제거한다.

유의할 점은 삭제하는 노드이 바로 전 노드에서 가 다음 노드로 연결 노드를 바꿔줘야 한다.

 

tail 삭제하는 경우

- tail 전의 노드의 next 값을 null로 바꾼다.

- tail을 그 전으로 옮긴다.

 

head 삭제하는 경우

head의 값을 head.next로 지정한다.

function SLL.delete_front()
  SLL.head = SLL.head.next

 

num과 일치하는 노드를 삭제하는 경우

function SLL.delete(num)
  set node = SLL.head
  while node.next.data != num:
    node = node.next
  
  node.next = node.next.next

탐색

head와 tail까지 이동한 이유는 탐색을 원활히 하기 위함이다.

단일 연결리스트에서 시작부터 끝을 확실히 해줘야 시작점에 해당하는 head부터 출발해 tail이 나오기 전까지 next를 따라가며 탐색을 진행할 수 있다.

 

참고