(191117) 자료구조 - Linked list

정리하면서 느낀점

핵심은 배열은 탐색은 O(1),탐색은 O(n)!!, 특정 index값 추출이 O(1), 데이터의 삭제 및 추가는 O(n)

연결리스트는 탐색은 O(n), 데이터의 삭제 및 추가는 O(1) 인듯....

(블로깅 하는데 너무 몰입하지말자...시간 너무 많이 씀....)

 

연결 리스트 (Linked list)

연결리스트에 대해 알아보기전에 배열과 연결리스트를 비교해보자.

 

배열 (array) - 데이터가 연속적으로 저장되어 있음

 

장점

1. 특정 데이터(엘리먼트)에 접근할 때 인덱스를 사용하여 매우 빠르고 간단하게 접근할 수 있다.

 

단점

1. (컴파일언어?에서) 배열을 사용하기 위해서는 배열의 크기를 미리 선언해야하고 크기의 수정이 불가능하기 때문에 메모리 관점에서 비효율적이다.

2. 중간에 데이터를 삽입하거나 제거하는 등 데이터의 이동 및 재구성이 매우 번거롭고 어렵다. (데이터들의 인덱스를 전부 바꿔줘야함?!)

 

연결리스트(linked list) - 데이터가 배열처럼 순차적으로 저장되어 있긴 하지만 메모리상에서 연속적으로 위치하여 있지는 않다.

즉, 노드라고 불리는 것 안에 데이터와 다음 노드를 가리키는 주소가 들어있고 이 노드들이 줄지어서 연결되어있는 형태

 

장점

1. 데이터의 삭제 및 추가 시에 배열과는 다르게 중간에 넣거나 삭제할 때 그 다음 노드를 가리키게만 하면되므로 데이터 재구성에 용이하다.

2. 또한 1번의 특징으로 메모리 관점에서 효율적이다. (배열과는 다르게 필요할 때 마다 메모리를 할당하여 사용 가능)

 

단점

1. 배열과는 다르게 특정 데이터를 검색하려면 연결 리스트의 처음부터 끝까지 탐색하여 찾아야 하므로 특정 데이터를 불러내기 어렵고 탐색 속도가 떨어진다.

 

 

이러한 특징으로 어떠한 자료를 저장할 때 탐색이나 데이터의 정렬을 자주 하는 경우에는 배열을 사용하는 것이 좋고,

데이터의 추가/삭제가 많은 경우에는 연결리스트를 사용하는 것이 좋다.

 

노드(Node)

연결 리스트는 노드로 이루어져 있는데 노드안에는 데이터를 저장하는 공간과 다음 주소를 가리키는 공간이 있다.

사용자가 입력하는 정보는 데이터 공간에 담고, 그 다음으로 노드가 추가 될 때마다 그 노드를 가리키는 주소를 담는다.

 

단순 연결 리스트 (Singly linked list)

연결리스트.jpg

연결리스트의 기본 형태이다. head 노드로 시작하여 마지막 tail 노드까지 데이터 들이 순차적으로 연결되어 있고, 마지막 tail 노드는 null 을 가리키고 있다.

 

property / method

먼저 연결리스트에 접근하기 위해서는 맨 처음 노드의 주소를 가르킬 노드가 필요한데 이 노드를 head 라고 한다. 또한 연결리스트에 맨 마지막 노드는 null을 가리키고 있고 이 노드를 가리키는 노드를 tail 이라고 한다. (위 그림에는 실수로 표시하지 않음)

 

연결리스트의 method로는 먼저 크게 리스트에 노드를 넣는 insert,  리스트에서 노드를 제거하는 remove, 데이터를 탐색하여 찾고자하는 노드를 찾아 해당 노드를 반환하는 find, 리스트가 비었는지 확인하는 empty, 리스트의 크기를 확인하는 size가 있다.

 

처음 연결 리스트 생성 시

1. head 노드를 만들고 null를 가리키게 한다.

2. tail 노드를 만들고 null를 가리키게 한다.

 

insert - 3가지 방법

- 리스트의 맨 뒤에 추가하는 경우

1. 리스트가 비어있다면

  1-1. head가 새로 추가되는 노드를 가리키도록 한다.

  1-2. tail이 새로 추가되는 노드를 가리키도록 한다.

  1-3. 새로 추가되는 노드가 null을 가리키도록 한다.

2. 리스트가 비어 있지 않다면

  2-1. tail 노드가 가리키고 있는 노드가 새로 추가되는 노드를 가리키도록 한다.

  2-2. 새로 추가되는 노드가 null을 가리키도록 한다.

  2-3. tail 노드가 새로 추가되는 노드를 가리키도록 한다.

 

- 리스트의 맨 앞에 추가하는 경우

1. 리스트가 비어있다면

  1-1. head가 새로 추가되는 노드를 가리키도록 한다.

  1-2. tail이 새로 추가되는 노드를 가리키도록 한다.

  1-3. 새로 추가되는 노드가 null을 가리키도록 한다.

2. 리스트가 비어 있지 않다면

  2-1. 새로 추가되는 노드가 head가 가리키던 노드를 가리키게 한다.

  2-2. head가 새로 추가되는 노드를 가리키게 한다.

 

- 중간에 노드를 추가하는 경우 (해당 노드의 뒤에 넣는다고 생각)

1. find를 통해 노드를 추가할 위치의 노드를 찾는다.

2. 해당 노드가 새로 추가되는 노드를 가리키도록 한다.

3. 새로 추가되는 노드가 해당 노드가 가리키고 있던 노드를 가리키도록 한다.

 

remove

- 특정 위치 데이터의 경우

1. head 부터 특정 위치까지 순차적으로 이동한다.

2. 해당 위치의 노드를 찾아간 후 해당 노드를 삭제하고 해당 노드를 가리키고 있던 노드 (이전 노드)가 해당 노드가 가리키고 있던 노드를 가리키게 한다.

 

- 특정 데이터의 경우

1. head부터 tail까지 이동하면서 노드가 데이터를 갖고 있는지 확인한다.

2. 해당 노드가 데이터를 갖고 있을 경우, 위에 2번과 동일한 과정

 

- 맨 뒤에 있는 데이터의 경우

1. tail이 가리키고 있는 노드를 삭제한다.

2. tail이 가리키고 있는 노드를 가리키는 노드(이전 노드)가 null을 가리키도록 한다.

3. tail이 이전 노드를 가리키도록 한다.

 

find

1. head부터 tail까지 이동하면서 해당 노드가 찾으려는 데이터를 갖고 있는지 확인한다.

2. 해당 노드가 데이터를 갖고 있을 경우, 해당 노드를 리턴

 

empty

만약 head가 null을 가리키고 있다면 true를 반환, 아니면 false 반환

 

size

head부터 tail까지 순차적으로 이동하면서 count 하여 tail까지 도착한 후 count값 리턴

 

이중 연결 리스트 (Doubly linked list)

이중 연결 리스트.jpg (위키)

노드가 다음 노드를 가리킬 뿐만 아니라 이전 노드도 가리키도록 되어 있다.

단일 연결 리스트에 비해 노드를 삭제하는 것이 훨씬 간단하다.

 

원형 연결 리스트(Circular linked list)

원형 연결 리스트.jpg (위키)

단순 연결 리스트에서 마지막 (tail)이 null이 아닌 처음 노드를 다시 가리키도록 되어 있다.

이중 연결 리스트도 마지막과 처음을 이으면 이중 원형 연결 리스트를 만들 수 있다.