[About 자료구조] 2.Linked List

0. 배열의 단점.

앞선 시간에 우리는 배열에 대해 공부하였습니다.
그런데 배열의 단점은 크게 두가지가 있습니다.
1. 배열의 크기가 가변적이지 않다.
2. 배열 내부의 원소를 추가 또는 삭제를 할려면 원소들을 이동시키는데에 있어서 시간이 소요된다.

그래서 이런 점을 보안한 Linked List라는 자료구조를 소개한다.

1. 링크드 리스트란 무엇인가요?

Linked List란 선형구조의 형태로 형성되는 node의 집합이라고 한다.
각 노드는 데이터를 담당하는 부분과 다음 node의 주소를 참조하는 부분으로 나누어져있다.
Singly Linked List(단일 연결 리스트)는 다음과 같은 형식으로 이루어져있다.

위와 같은 그림에서 첫번째 node를 Head , Null(맨 마지막)을 가리키는 node를 Tail이라고 부른다.

만약 Singly Linked List의 Tail을 찾기위해서는 Head에서 시작하여 다음 Node를 찾아가는 과정을 반복하여 Tail을 찾을 수 있는데 위와 같은 방법을 Link hopping 또는 Pointer Hopping 이라 부른다.

2. 링크드 리스트에 노드 추가하는 방법

Case 1. Head에 새로운 Node 추가(PseudoCode로 작성)

 Algorithm addFirst(e){
 	newNode = Node(e)
    newNode.next = head
    head = newNode
    size = size+1
    }

1. 새로운 Node를 newNode 로 만든다.
2. newNode의 다음 node를 head로 설정한다.
3. head를 newNode로 설정한다.
4. Linked List의 크기를 1 증가시킨다.

Case 2. Tail에 새로운 Node 추가(PseudoCode로 작성)

Algorithm addLast(e){
	newNode = node(e)
    tail.next = newNode
    tail = newNode
    size = size+1

1. 새로운 node를 newNode라고 한다.
2. tail의 다음 가리키는 node를 newNode로 한다.
3. tail을 Newnode로 칭한다.
4. Linked list의 크기를 1 증가시킨다.

3. 링크드 리스트의 장단점

장점

크기가 가변적이어서 자료를 내가 원하는 만큼 넣거나 뺄수 있다.

단점

1. 자료를 담는 부분과 다음 Node의 주소를 가리키는 부분이 있어서 한 Node당 크기가 배열때의 크기보다 커진다. 따라서 메모리가 한정되어 있는 상황에서는 구현이 힘들 수 있다.
2. 자료를 찾는 과정에 있어서 배열은 각 원소마다 index가 있어서 쉽게 찾을수 있으나, Linked List 에서는 Head에서 시작하여 찾아야 하기 때문에 소요되는 시간이 길어질 수 있다.

4. 링크드 리스트의 종류

Circular Linked List

Circular Linked List란 Singly Linked List와 Tail의 다음 Node를 가리키는 주소를 Head로 가리키게 하는 점을 합친 Linked List를 말한다.

Double linked List

Double Linked List란 데이터를 담는부분, 다음 Node의 주소를 담는부분 , 이전 Node의 주소를 담는 부분을 포함한 Node로 이루어진 Linked List를 말한다.
위 그림에서는 Prev는 이전 Node에 대한 주소를 담는부분, Next는 다음 Node에 대한 주소를 담는 부분을 말한다.