DataStructure - Linked List

 

안녕하세요 BeePeach입니다 :)

오늘 공부해볼 자료구조는 linked list(연결 리스트)입니다.

 

이전에 공부해봤던 배열의 단점은 미리 데이터 공간을 확보해야 한다는 점입니다.

그래서 데이터에 정보를 추가시키려는데 공간이 작다면 다른 곳에 더 큰 데이터 공간을 확보시키고 데이터를 옮기는 작업이 이루어집니다.

 

Linked List는 데이터공간을 미리 확보하지 않고 흩어져있는 데이터 공간들을 연결시킵니다.

 

하지만 단점도 존재하겠죠?

• 주소를 저장하는 별도의 데이터 공간이 필요합니다.
• 원하는 데이터를 찾을때 앞에서 또는 뒤에서부터 찾아가야 합니다.
• 중간의 데이터를 삭제하면 양쪽 데이터를 연결시켜주어야 합니다.

 

그럼 코드로 한번 만들어보겠습니다.

 

 

---

 

Node

 

배열은 데이터만 저장을 하죠??

LinkedList는 데이터뿐만 아니라 다음 데이터의 주소도 저장해야 합니다.

 

그렇다면 데이터를 부르는 새로운 단위를 정하는 게 좋습니다.

Linked List의 Node(노드)란 Data + Pointer를 의미합니다.

Pointer란 다음 또는 이전 노드의 주소를 의미합니다.

 

다시 말해서 linked list는 노드를 저장한 데이터 구조입니다.

 

맨 앞 노드를 head라고 지칭하고 맨 앞의 노드의 주소만 알고 있다면 모든 노드들의 주소를 알 수 있게 됩니다.

노드에 다음 노드의 주소가 저장되어있을 테니까요!

그리고 pointer의 값이 nil이 되면 이 노드가 마지막 노드인 것을 할 수 있습니다.

 

맨 뒤 노드는 tail이라고 합니다.

 

 

	class Node<T: Equatable> {
	var data: T
	var next: Node?
	init(_ data: T) {
	self.data = data
	}
	}

view raw Algorithm_LinkedList_Node.swift hosted with ❤ by GitHub

next에는 다음 노드의 주소가 저장됩니다.

타입 파라미터 T가 Equtable 프로토콜을 채용하도록 한 것은 이후에 data를 이용해서 노드를 삭제하는 기능을 구현하기 위해서입니다.

 

 

---

 

LinkedList

 

 

	class LinkedList<T: Equatable> {
	var head: Node<T>?
	func printData() {
	// 헤더 체크
	guard var node = head else {
	print("Don't exist Head")
	return
	}
	// 마지막까지
	while let next = node.next {
	print(node.data, terminator: " ")
	node = next
	}
	print("\nFin")
	}
	}

view raw Algorithm_LinkedList_Basic.swift hosted with ❤ by GitHub

기본적인 구현은 head를 정해줍니다.

물론 무조건 head가 있도록 구현하고 옵셔널을 뺄 수 도있지만 삭제를 고려하여 넣어줬습니다.

 

LinkedList를 볼 수 있도록 print를 구현했습니다.

먼저 head가 없다면 반복할 필요가 없으니 체크를 해줍니다.

 

그 후에 node.next가 nil이라면 tail이라는 의미이고 여기가 바로 LinkedList의 마지막 부분입니다.

 

 

---

 

append

 

	func append(data: T) {
	guard var node = head else {
	print("Don't exist Head")
	return
	}
	while let next = node.next {
	node = next
	}
	node.next = Node(data)
	}

view raw Algorithm_LinkedList_Append.swift hosted with ❤ by GitHub

Append는 맨뒤에 노드를 추가하도록 합니다.

print와 마찬가지로 node.next가 nil이라면 tail이므로 while문으로 tail까지 이동한 뒤에 next에 새로운 노드를 연결시켜줍니다.

 

 

---

 

delete

 

 

	func delete(data: T) {
	// Head 체크
	guard var node = head else {
	print("Don't exist Head")
	return
	}
	// 1. Head가 삭제할 데이터일때
	if node.data == data {
	head = nil
	head = node.next
	} else {
	while node.next != nil {
	//2, 3. 다음 데이터가 삭제할 데이터 일때
	if node.next?.data == data {
	// 재연결 한 뒤에 해당 노드 삭제
	var temp = node.next
	node.next = node.next?.next
	temp = nil
	} else {
	// next가 절대 nil일 수 없다.
	guard let next = node.next else {
	return
	}
	node = next
	}
	}
	}
	}

view raw Algorithm_LinkedList_delete.swift hosted with ❤ by GitHub

 

삭제는 data 기준으로 맨 앞의 data를 삭제하도록 구현했습니다.

그럼 노드가 삭제될 때 고려해야 할 부분은 3가지입니다.

 

1. 삭제될 노드가 head일 때

2. 삭제될 노드가 중간에 위치할 때

3. 삭제될 노드가 tail일 때

 

첫 번째 경우에 head가 삭제되면 head를 변경해주어야 합니다.

그래서 head에 연결된 노드를 nil로 삭제시킨 뒤에 next를 head로 설정해주었습니다.

 

두 번째 경우에는 먼저 일치하는 data를 

중간 노드를 삭제하고 나서 연결을 다음 노드로 이어주었습니다.

이때 삭제될 노드를 임시로 저장할 temp를 선언했습니다.

 

세 번째 경우에는 삭제할 노드가 tail이라면 삭제한 뒤에 이전 노드의 next를 nil로 만들어주어야 합니다.

그런데 여기서 2번째 경우와 3번째 경우는 한 번에 처리할 수 있습니다.

 

 

---