링크드 리스트란
: 리스트를 구현하는 여러 가지 기법 중에서도 가장 간단한 방법으로 꼽히는 자료구조
리스트 내의 각 요소는 노드(Node)라고 부릅니다. 노드는 우리말로 '마디'라는 뜻인데, 링크드 리스트는 '노드를 연결해서 만드는 리스트'라고 해서 붙여진 이름이다.
링크드 리스트의 노드는 데이터를 보관하는 필드와, 다음 노드와의 연결 고리 역할을 하는 포인터로 이루어진다.
리스트는 헤드(Head)와 테일(Tail)을 갖고 있습니다. 리스트의 첫 번째 노드를 헤드라 하고 마지막 노드를 테일이라고 한다.
링크드 리스트의 주요 연산
- 노드 생성/소멸
- 노드 추가: 링크드 리스트의 테일 노드 뒤에 새로운 노드를 만들어 연결하는 것
- 노드 탐색: 링크드 리스트가 갖고 있는 약점 중 하나이다. 헤드부터 시작해서 다음 노드에 대한 포인터를 징검다리 삼아 차근차근 노드의 수를 세어나가야만 원하는 요소에 접근할 수 있음
- 노드 삭제: 링크드 리스트 내에 있는 임의의 노드를 제거하는 연산
- 노드 삽입: 노드와 노드 사이에 새로운 노드를 끼워넣는 연산
생성/소멸, 추가, 삭제, 삽입은 링크드 리스트 자료구조를 구축하기 위한 연산이다. 리스트 탐색은 구축되어 있는 링크드 리스트의 데이터를 활용하기 위한 연산입니다.
링크드 리스트의 단점
- 다음 노드를 가리키려는 포인터 때문에 각 노드마다 4byte의 메모리가 추가로 필요하다.
- 특정 위치에 있는 노드를 얻는데 드는 비용이 크며 속도도 느리다. 노드의 개수가 n이라면 최악의 경우 n회의 노드 탐색 루프를 실행해야 특정 위치에 있는 노드를 찾을 수 있다. 반면 배열은 상수 시간에 노드를 얻을 수 있다.
상수 시간: 어떤 문제를 풀이하는데 필요한 수학적 연산 시간이 주어진 입력 자료에 관계 없이 일정할 때의 연산 시간 의미
링크드 리스트의 장점
- 새로운 노드의 추가/삽입/삭제가 쉽고 빠르다. 배열은 요소를 삽입하거나 제거하기가 어렵다.
- 현재 노드의 다음 노드를 얻어오는 연산에 대해선느 비용이 발생하지 않는다(이것은 장점이라고 하기는 어렵지만, 단점은 확실히 아니기에 장점으로 분류)
장단점을 정리
노드의 추가/삽입/삭제는 빠르나 특정 위치에 있는 노드를 찾는 연산은 느리다라고 할 수 있다. 따라서 링크드 리스트가 사용되기에 적합한 곳은 레코드의 추가/삽입/삭제가 잦고 조회는 드믄 곳이다. 데이터베이스에서 조회해온 레코드를 순차적으로 다루는 데에는 아주 제격이다.
더블 링크드 리스트
링크드 리스트의 탐색 기능을 개선한 자료구조이다. 링크드 리스트에서는 노드를 찾으려면 헤드에서 테일 방향으로만 탐색을 할 수 있는데 반해 더블 링크드 리스트는 양방향으로 탐색이 가능하다는 것이다.
더블 링크드 리스트는 리스트의 노드는 자신의 앞에 있는 노드를 가리키는 포인터도 갖고 있습니다. 이로 인해 뒤로 이동할 수 있을 뿐만 아니라 앞으로도 이동할 수 있다.
더블 링크드 리스트의 주요 연산
(링크드 리스트 연산과 다른 것은 없다. 다만 이전 노드를 처리하기 위한 구현이 더 추가될 뿐이다.)
- 노드 생성/소멸
- 노드 추가: 링크드 리스트의 테일 노드 뒤에 새로운 노드를 만들어 연결하는 것
- 노드 탐색: 링크드 리스트가 갖고 있는 약점 중 하나이다. 헤드부터 시작해서 다음 노드에 대한 포인터를 징검다리 삼아 차근차근 노드의 수를 세어나가야만 원하는 요소에 접근할 수 있음
- 노드 삭제: 링크드 리스트 내에 있는 임의의 노드를 제거하는 연산
- 노드 삽입: 노드와 노드 사이에 새로운 노드를 끼워넣는 연산
환형 링크드 리스트
환형 링크드 리스트는 머리가 꼬리를 물고 있는 형태의 링크드 리스트이다.
환형 더블 링크드 리스트의 주요 연산
1. 테일은 헤드의 '앞 노드'이다
2. 헤드는 테일의 '뒷 노드'이다
환형 더블 링크드 리스트와 그냥 더블 링크드 리스트의 차이는 바로 위 두 가지 사항이 사실상 전부이다.
주요 연산
- 노드 추가
- 노드 삭제
