[자료구조] 연결 리스트(Linked List)

이번 포스팅에선 연결 리스트(Linked List)에 대해 살펴볼 것이다.

먼저 데이터를 삽입하는 방법은 두 가지가 있다.

1. 필요할때마다 메모리를 할당받아 데이터를 저장하는 방법.

2. 미리 메모리를 확보한 다음 연속된 공간에 저장하는 방법.

 

여기서 1번이 연결리스트의 데이터 삽입 방식이다.

연결 리스트는 낭비되는 데이터는 없지만 연관된 데이터끼리 연결 짓는 것이 필수적이고 중요하다.

연결 리스트란?

연결 리스트는 두 개의 필드로 이루어진 node가 기본 단위이다.

node는 데이터를 저장하는 데이터 필드와 다음 노드를 가리키는 링크 필드로 구성된다.

node는 서로 다른 데이터 타입을 하나로 묶으므로 class에 해당된다.

따라서 링크필드에 해당하는 것은 class 포인터이다.

이를 노드형 포인터라고도 한다.

 

일반적으로 첫번째 노드를 head라고 하며, 헤드의 주소를 변수 head 담아 보관한다.

마지막 노드를 tail 이라 하며, 테일의 주소를 변수 tail에 담아 보관한다.

이때 변수 head, tail은 노드의 주소를 저장하므로 노드형 포인터다.

 

node는 동적으로 할당되고 포인터를 기반으로 구현되므로 필요로 하는 메모리의 크기에 맞게 유연하게 대처가 가능하다.

링크드 리스트는 단일 연결리스트연결 리스트 (Singly Linked List), 이중 연결 리스트 (Doubly Linked List), 원형 연결 리스트가 있다.

 

단일 연결 리스트는 head ⇒ tail 의 방향으로 다음 노드의 주소만 갖지만, 이중 연결 리스트는 head <=> tail의 방향으로 이전과 다음 노드의 주소를 모두 갖는다.

 

이 포스팅에선 단일 연결 리스트에 대해 살펴볼 것이다.

 

단일 연결 리스트의 탐색

링크드 리스트는 배열처럼 메모리공간에 정렬되어있지 않고 사방에 흩어져 존재한다.

따라서 배열처럼 특정 노드에 바로 접근할 수 없다.

ex. 1~10번 노드가 있는데 4번노드에 접근하려고 하면 1번부터 4번까지 탐색해야만 한다.

링크드 리스트는 무조건 헤드에서 시작해야 한다.

 

단일 연결 리스트의 삽입

링크드 리스트의 데이터에 접근하려면 헤드에서부터 시작해야 한다.

 

1. 헤드 앞에 인서트

새로운 노드 생성

→ 생성된 노드의 링크필드가 기존 헤드를 가리키도록 설정 (매달린 상태)

→ 새로운 노드를 헤드로 지정

→ 링크드 리스트 크기 1 증가

 

2. 테일 뒤에 인서트

새로운 노드 생성

→ 기존 테일의 링크필드가 새로운 노드를 가리키도록 수정 (매달린 상태)

→ 새로운 노드를 테일로 지정

→ 링크드 리스트 크기 1 감소

 

단일 연결 리스트의 삭제

1. 헤드를 삭제

기존 헤드를 담을 변수 생성

→ 변수 이용해서 헤드의 next를 헤드로 지정

→ free나 delete 키워드로 기존 헤드 삭제

cf. 기존 헤드를 삭제하지 않으면 데이터 누수가 발생함

 

2. 테일을 삭제

기존 테일의 이전 노드가 null을 가리키도록 수정

→ 이전노드를 새로운 테일로 지정

→ 기존 테일 값 삭제

cf. 테일을 삭제하려면 테일 이전 노드의 주소를 알기 위해 헤더에서부터 next를 반복해야 한다.

이처럼 싱글리 링크드 리스트에서 테일을 삭제하는 건 비효율적이다.

but, 더블리 링크드 리스트는 이전 노드의 주소로 접근하면 되므로 바로 할 수 있다!