[자료구조]chapter2-lesson3. 단일 연결 리스트

 

삽입과 삭제를 많이 하는경우 해당 코드는 비효율적이게 된다. 

이러한 문제를 해결하기 위해 연결  리스트라는 새로운 자료구조가 등장하게 된다 ! 

 

연결리스트 

 

-탐색은 느리다. O(N)

-삽입과 삭제 연산은 매우 빠르다 O(1)

-삽입과 삭제가 잦은 상황에서 자주 사용된다. 

- 여러개의 노드가 모여서 형성되는 구조

노드란

- 연결리스트를 알기위해 이해해야 하는 개념

- 정보를 담는 하나의 창구라고 생각하면 된다. 

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

단일연결리스트

 

- 단일 = 연결방향이 단방향 = 일방통행 구조

- 바로 옆 노드를 참조할 수 있음. 

단일 연결리스트의 노드가 갖고 있는 다른 노드의 참조

- 각 노드별로 data와 next값을 가지고 있는데 data 는 값을 next는 다음 노드의 위치를 가르키는 역할 

- 예를 들어 값이 4인 노드가 있다면 다음 노드가 없기 때문에 next에는 기본적으로 null이 들어있다. 

- 수도 코드를 이용하여 node1과 node2를 만들고 이를 연결해보자.

#node1을 만든다. 
set node1 = node(3)

#node2를 만든다. 
set node2 = node(5) 

# node1과 node2를 연결한다. 
node1.next=node2

#node1.next는 node2 자체를 의미한다. 

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

 

- node1과 node2를 분리해보자.

node1.next = null # 두 관계를 끊는다.

 

- next 값에 null을 넣는 것은 뒤에서 노드를 삭제할때 이용하게 된다. 

 

단일연결리스트의 문제점 : 시작점을 찾을 수 없음. 

 

-시작점을 알지 못한다면 우리가 모든 값을 탐색했는지 판단할 수 없음. 

- 그래서 리스트의 첫번째 값의 위치를 반드시 명시해야 함. -> 이를 head라고 부름. 

- 종료되는 시점도 명시 -> tail이라고 함. 

- 단일연결리스트는 삽입 삭제 탐색이 모두 가능한 자료구조

-탐색의 경우 ,  head부터 tail을 일일히 확인해야 하므로 O(N)이라는 시간이 소요된다.  

-하지만 삽입과 삭제의 경우 인접한 곳의 선을 끊고 연결해주는 작업만 하면 되므로 O(1)의 시간이 소요된다. 

- 뒤로 돌아갈 수 없는 구조

 

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

 

<삽입>
- tail 은 next가 비어있기 때문에 새로운 노드가 들어오게 되면 next가 가리키는 노드를 해당 노드로 지정해주면된다. 
- 그러나 새로운 노드는 tail보다 뒤에 위치 -> 추가적으로 tail이 가리키는 노드를 변경해줘야 함. 

# tail 뒤에 삽입하는 코드 
function SLL.insert_end(num) 
	set new_node = node(num) # 1. 노드 만들기 
    SLL.tail.next = new_node # 2. 이어 붙이기 
    SLL.tail = new_node # 3. Tail 변경하기​

# head앞에 삽입하는 코드 
function SLL.insert_front(num) 
    set new_node = node(num) # 1. 노드 만들기 
    new_node.next = SLL.head # 2. 이어 붙이기 
    SLL.head = new_node # 3. head 변경하기

# head바로 뒤에 노드를 삽입하는 경우 
function SLL.insert_after_head(num) 
	set new_node = node(num) # 1. 노드 만들기 
    new_node.next = SLL.head.next # 2. 새로운 노드의 next 값 변경
    SLL.head.next = new_node # 3. head의 next값 변경

<삭제>
- 연결을 제거 
- 삭제되는 노드의 바로 전 노드에서 그 다음 노도로 연결관계를 변경해줘야 함. 
- tail 삭제 시, tail 바로 전 노드의 next 값을 먼저 null로 변경한 뒤 tail을 그 전으로 옮겨주는 작업을 함. 
- head 삭제 시, head의 값을 head.next로 지정하기만 하면 됨. 

<탐색>
- 단일 연결리스트는 시작과 끝이 명확해야 시작점부터 끝점까지 next를 따라가며 탐색을 진행할 수 있음.