본 내용은 공부를 위한 내용으로 틀린내용이 있을수 있습니다.
앞에서는 일반 배열이 아닌 연결리스트를 사용하는 알아보았다.
이제 연결리스트를 위한 연산이 어떻게 있는지에 대해 공부해보자.
YODA: 하거나, 하지 말거나. 해보기만 하는 건 없지.
그래!! 직접 해보는거야!! 잉?? 아.. 아니 하는거야!!
연결리스트 Insert 연산을 알아보아요.
일단 각 Node 는 다음처럼 생겨먹었다
interface Node {
data: string
link: Node
}Node 의 data 프로퍼티는 값을 담고 있으며, link 는 다음 연결된 Node 의 주소를 가진다고 생각하면 된다.
Node 에 대해 확인했으니 이 Node 를 연결리스트를 통해 어떠한 구조로 연결되었는지 그림을 통해 확인해보자.
위는 week 라는 linked list 를 가정해서 이야기한다.
여기서 첫번째 사각형은 data 이며, 두번째 사각형은 link 를 담는 property 라 생각하자.
Linked List 는 내부에 head 라는 property 가 존재한다.
이 head 를 출발점으로 하여 다음 노드와 연결되는 구조이다.
끝은 tail 이라 부르며, 다음 연결 노드가 없어 link 는 항상 null 이다.
즉 다음처럼 되어 있다고 보면 된다.
interface Node {
data: string
link: Node
}
const week: LinkedList =
head
--> { data: '월', link: 0x210 }: Node // 객체 주소: 0x100
--> { data: '수', link: 0x300 }: Node // 객체 주소: 0x210
--> { data: '금', link: null }: Node // 객체 주소: 0x300
이렇게 head 를 기점으로 해서 해당 tail 까지 Node 객체의 link 가 서로 연결되어 있는 구조이다.
이를 class 로 나타낸다면 다음과 같을 것이다.
public class LinkedList {
constructor(head: null | Node = null) {}
insert: void() {}
delete: void() {}
print: void() {}
search: Node() {}
// ....
}
위의 LinkedList 를 구현하기 위해 insert 를 구현해보자.
Insert
insert 에 대해 알아보기 위해서는 LinkedList 가 어떻게 추가 되는지 확인해보자.
Insert Last Node
우리는 javascript 의 push method 를 알고 있을 것이다.
이 push method 는 배열의 마지막에 원수를 추가할때 사용하는 배열의 native method 이다.
const arr = [];
arr.push(1);
arr.push(2);
console.log(arr); // [1, 2]
LinkedList 에도 원소를 추가해야 하므로, 마치 push 처럼 원소를 추가해보도록 하자.
해당 로직을 구성하기 위해서는 LinkedList 는 다음과 같은 순서로 연결된다.
1) 새로운 Node 인 new 를 만든다. 여기서 주의할 점은 new Node 의 link 는 마지막에 삽입되므로 NULL 이어야 한다.
2) new 인 Node 는 마지막에 삽입되어야 하니 Tail 인 Node 의 link 는 new Node 를 가리킨다.
3) 그럼 마치 배열의 push 처럼 다음처럼 Linked List 가 만들어진다.
위 로직을 코드를 통해 구현해본다.
interface Node {
data: stirng
link: Node | null
}
class LinkedList {
constructor(private head: Node | null = null) {}
public insertLastNode(data: string) {
const newNode: Node = { data, link: null }
if (this.head == null) this.head = newNode
else {
let tmp: Node = this.head
while(tmp.link != null) {
tmp = tmp.link
}
tmp.link = newNode
}
}
}
위 로직중 다음을 보자
if (this.head == null) {
head = newNode
}
이 로직은 head 값이 null 이면 마지막에 들어가는 노드역시 head 일 것이니 head 는 newNode 가 된다.
다음은 head 가 null 이 아닐때 의 로직이다.
else {
let tmp: Node = this.head
while(tmp.link != null) {
tmp = tmp.link
}
tmp.link = newNode
}
위의 코드는 tmp 라는 변수를 만들고 head 를 할당한다.
실제 head 값은 Linked List 의 첫번째를 가리키니 변경되면 안된다.
let tmp: Node = head
그러므로 해당 주소값을 tmp 에 할당하여 tmp 를 통해 변경되도록 한다.
while(tmp.link != null) tmp = link
while 문을 통해 tmp 에 연결된 link 를 순회한다.
tmp.link 값이 null 이면 whil 문은 순회를 멈춘다.
tmp.link = newNode
순회된 tmp 의 link 는 값이 null 이다.
null 값을 가진 tmp 는 더이상 마지막 노드가 아니므로 해당 link 에 newNode 를 할당한다.
간단히 말하면 새롭개 만든 Node 를 마지막 link 에 연결하는 방법을 통해 로직을 구현할 수 있다.
참 쉽죠??
다음은 중간에 Node 를 삽입해보자.
Insert Middle Node
insert middle node 는 중간에 노드를 삽입하는 방식을 말한다.
아래의 방식을 보자.
javascript array 를 통해 말하자면 다음과 비슷할 것이다.
const arr = [1, 2, 4];
arr.splice(2, 0, 3); // [1, 2, 3, 4]
Node 중간에 값을 삽입하기 위해서는 다음과 같은 순서로 처리 될것이다.
1) 일단 insert 하기 위해 새로운 Node 인 new 를 만든다.
2) 다음에 new Node 의 link 에 다음 연결한 Node 의 주소를 할당한다.
3) 월요일을 데이터로 가진 노드의 link 는 new 노드의 주소를 할당한다.
4) 그럼 다음과 같이 연결리스트가 이루어진다.
이를 구현해보자.
일단 이 insert method 가 작동하기 위해서는 중간에서 삽입이 이루어지니 insertMiddleNode 라 명한다.
interface Node {
data: string
link: Node
}
type NodeType = Node | null
class LinkedList {
constructor(private head: Node | null = null) {}
public insertMiddleNode(preNode: NodeType, data: string) {
console.log(preNode);
if (preNode == null) return
const newNode: Node = { data, link: null }
newNode.link = preNode.link
preNode.link = newNode
}
}
위의 로직을 보면 중간에 삽입할 node 가 필요하다.
삽입 node 를 parameter 를 통해 할당하며, 새롭게 만들어질 Node 의 값을 삽입하기 위해 data parameter 를 만든다.
여기에서 preNode 는 Node 가 아닌 NodeType 으로 지정했는데, 이는 preNode 가 null 일때를 가정하여 type 지정했다고 생각하면 된다.
public insertMiddelNode(preNode: NodeType, data: string) {}
처음으로 pre 가 null 이면 insert 할 필요가 없기에 바로 return 하여 밑의 logic 이 작동하지 않도록 만든다.
실제 preNode 가 null 이 아니라면 Node console.log 로 찍어보았다.
if (preNode == null) return
console.log(preNode)null check 로직이후 새로운 newNode 를 만든다.
const newNode: Node = { data, link: null }
newNode 의 link 는 preNode.link 를 향한다.
그런후 preNode 의 link 는 newNode 를 향하면 중간에 newNode 가 연결된다.
newNode.link = preNode.link
preNode.link = newNode
쉽게 Node 가 중간에 삽입되었다.
OK?
지금까지 Insert 연산에 대해 알아 보았다.
뭐 Insert 연산 자체는 그렇게 어렵지 않았다.
TO BE CONTINUED
다음은 Delete 연산에 대해 알아보자.
