[자료구조] Linked List, Double Linked List

Linkded List

• 노드가 데이터와 링크를 가지고 한줄로 연결되어있는 방식

장점

1. 추가/삽입/삭제에 용이하다.(포인터만 바꾸면 되기때문)
   • 배열은 추가/삭제/삽입 시 한쪽으로 땡겨주거나 옆으로 다 옮겨야함
2. 연속적인 기억 장소에 할당안해도 된다.

단점

1. 탐색 속도가 느리다. (순차 탐색)
   • 배열은 인덱스로 접근하기 때문에 탐색 속도가 빠르다.

length

1. cursor 포인터를 만들고, cursor가 head랑 같은 노드를 가리키게한다.
2. 그리고 cursor는 다음 노드 포인터가 null을 만날 때 까지(노드 끝까지) 루프를 돌면서 카운팅한다.

head insert

1. new 노드에 데이터를 초기화한다.
2. 그리고 new 노드의 next는 현재 head가 가리키는 노드를 가리킨다.
3. head는 new 노드를 가리킨다.

insert (특정 위치)

1. 특정 위치 i+1 번째에 노드를 삽입하려고 한다.
2. 현재 i 번째에 있는 노드를 previous포인터로 가리킨다.
3. new 노드를 만들고, 데이터를 초기화한다.(new 노드를 insert포인터가 가리키고있다.)
4. new 노드의 next는 i 번째 노드(previous)의 next가 된다.
5. i 번째의 next는 insert포인터가 가리키는 new 노드가 된다.

search

1. target이 10이라고 하자
2. cursor포인터가 순회하면서 target을 찾는다.

locate

1. position값이 들어와서 해당 position의 노드를 검색한다.
2. cursor가 돌면서 index 늘려서 position을 찾는다.

remove head

1. remove포인터를 만들어서 head노드를 가리키게한다.
2. head포인터는 remove포인터가 가리키는 노드(현재 첫번째 노드)의 next를 가리킨다.
3. remove노드를 삭제한다.

remove

1. i+1번째의 노드를 삭제하려고 한다.
2. i번째 노드를 previous포인터로 가리킨다.
3. i+1번째 노드는 remove포인터로 가리킨다.
4. previous노드의 next는 remove노드의 next를 가리키도록한다.
5. remove노드를 제거한다.

clear

1. head remove를 실행한다. (빌때까지)

Double Linked List

위에 나오는 단순 linkedlist는 다음 노드에 대한 참조만 가지고 있어서 단방향 탐색밖에 못한다.

double linked list는 다음 노드와, 이전 노드 참조하여 양방향탐색이 가능하도록하여 검색속도를 향상시킬 수 있다.

단순 연결 리스트

• 다음 노드에 대한 참조만 가지고 있어서 단방향 탐색(순차 탐색)
• 검색하는 데이터가 리스트의 뒷 부분에 위치할 경우 순차 탐색
• 평균 접근이 데이터수/2

이중 연결 리스트

• 다음 노드의 참조와, 이전 노드의 참조를 가지고 있어서 양방향탐색이 가능하여 검색속도를 향상시킬 수 있다.
• 검색 데이터가 앞부분에 있으면 순방향 탐색을하고, 데이터가 뒷부분에 있을 경우 역방으로 탐색하게 된다. 따라서 단순 연결 리스트에 비해 두배 정도의 빠른 검색 효율을 갖는다.
• 검색 뿐 아니라, 사입, 삭제 경우에도 해당 위치의 앞, 뒤 노드를 꺼낸후, 참조 노드의 값을 수정하기 때문에 검색 작업이 먼저 이루어 지므로 이또한 효율이 좋아진다.

구조

• Header의 next는 첫번째 노드, prev는 마지막 노드를 가리킨다.(head- 첫번째 노드, tail- 마지막 노드)
• 첫번째 노드일 경우 prev-null값, next-null값

search

• index가 리스트의 size보다 중간보다 뒤면 역방향으로 탐색한다.

head insert

1. 새로운 노드의 next -> 첫번째 노드
2. 첫번째 노드의 prev -> 새로운 노드
3. head -> 새로운 노드

insert

1. i+1번째에 노드 삽입
2. i 번째 노드 next-> 새로운 노드
3. 새로운 노드 prev -> i 번째 노드
4. i+2 번째 노드 prev -> 새로운 노드
5. 새로운 노드 next -> i+2번째 노드

head remove

1. head -> 두번째 노드
2. 두번째 노드 prev -> null
3. 첫번째 노드 삭제

remove

1. i+1번째 노드 삭제
2. i+1번째 노드를 찾아서 앞뒤 노드를 가져온다.
3. i번째 노드 next -> remove 노드 next
4. i+2번째 노드 prev -> remove 노드의 prev
5. i+1번째 노드 삭제