[자료구조] Linked List

Linked List란?

각 노드가 데이터와 포인터를 가지고 한 줄로 연결되어 있는 방식으로 데이터를 저장하는 자료구조.

이름에서 말하듯이 데이터를 담고 있는 노드들이 연결되어 있는데, 노드의 포인터가 다음이나 이전의 노드와의 연결을 담당하게 된다.

연결 리스트의 종류로는 단일 연결 리스트, 이중 연결 리스트 등이 있다.

연결 리스트는 늘어선 노드의 중간지점에서도 자료의 추가와 삭제가 O(1)의 시간에 가능하다는 장점을 갖는다. 그러나 배열이나 트리 구조와는 달리 특정 위치의 데이터를 검색해 내는데에는 O(n)의 시간이 걸리는 단점도 갖고 있다.

(출처 : Wikipedia-연결리스트)

 

Linked List의 필요성

일반적으로 배열을 사용하여 데이터를 순차적으로 저장하고 나열할 수 있으나, 배열을 사용하는 경우 메모리 공간이 불필요하게 낭비될 수 있음. 기본적으로 초기에 배열 크기를 설정하면 변경이 불가능 하기 때문. 이럴 때 연결리스트를 이용해 메모리 낭비를 줄일 수 있음.

 

*자바스크립트는 해당되지 않음.

 

Array vs. Linked List 

Array	Linked List
∙ 특정 위치의 원소에 즉시 접근할 수 있음 ∙ 데이터가 들어갈 공간을 미리 메모리에 할당해야함 ∙ 원하는 위치에 삽입이나 삭제하는 것이 비효율적임	∙ 특정 인덱스로 접근할 수 없기 때문에, 원소를 차례대로 검색해야함 ∙ 필요할 때마다 메모리 공간을 할당받음 ∙ 포인터를 이용하여 리스트 중간에 노드를 추가하거나 삭제할 수 있음 *

* 추가적인 포인터 변수를 사용하기 때문에 메모리 공간이 낭비됨

 

Singly Linked List (단일 연결 리스트)

하나의 구조체 안에 두 개의 변수가 담김

1. 데이터를 담는 변수
2. 다음 노드를 알려주는 포인터

• Head : Linked List의 시작 노드로 별도로 관리함
• 마지막끝 노드는 Null을 가리켜 끝을 알림

 

노드 추가

기존 root가 가리키는 next값을 추가하려는 노드의 next값으로 할당. root의 next를 현재 노드로 변경함

 

이미지 출처 : Wikipedia

 

노드 삭제

앞의 노드가 삭제할 노드의 다음 노드를 가리키게 하고, 메모리 할당을 해제함

 

이미지 출처 : Wikipedia

 

Doubly Linked List (양방향 연결 리스트)

노드 앞, 뒤 정보를 모두 저장하고 있는 리스트로 Head와 Tail을 모두 가지고 있음

 

노드 추가

단일 연결리스트처럼 해주되 비슷한 방식으로 prev값도 할당을 해줌

prev = cur → prev;
prev → next = node;
node → prev = prev;
cur → prev = node;
node → next =cur

 

노드 삭제

단일 연결리스트처럼 해주되, next의 prev가 현재의 prev를 가리키도록 변경해줌.

head → next = node → next;
next → prev = head;

 

주의사항

• 삽입 및 삭제 기능 예외사항 처리 필요
• 삭제할 원소가 없는데 삭제하는 경우 등 체크 필요

 

 

 

 

 

 

 

참고 | Wikipedia, fast campus 컴퓨터공학 전공 필수