리스트
- 순서를 가진 데이터의 집합을 가리키는 추상 자료형으로 배열로 구현된 순차리스트와 메모리의 동적할당을 기반으로 구현된 연결리스트 두가지로 구현할 수 있다.
순차리스트
- 1차원 배열(단순 배열)에 항목들을 순서대로 저장한다.
- 단순배열을 이용한 순차리스트를 구현해 사용하는 경우, 자료의 삽입/삭제/ 연산 과정에서 연속적인 메모리 배열을 위해 원소들을 이동시키는 작업이 필요하다. 따라서 원소의 개수가 많고 삽입/삭제 연산이 빈번하게 일어날 수록 작업에 소요되는 시간이 크게 증가는 문제점이 있다.
연결리스트
- 자료의 논리적인 순서와 메모리 상의 물리적인 순서가 일치하지 않고, 개별적으로 위치하고 있는 각 원소를 연결하여 하나의 전체적인 자료구조를 이룬다.
- 링크를 통해 원소에 접근하므로, 순차 리스트에서처럼 물리적인 순서를 맞추기 위한 작업이 필요하지 않다.
- 자료구조의 크기를 동적으로 조정할 수 있어, 메모리의 효율적인 사용이 가능하다.
연결리스트 기본 구조
- 노드 : 연결 리스트에서 하나의 원소를 표현하는 블록
- 노드의 구성 요소 : 데이터 필드, 링크 필드
데이터 필드 : 원소의 값을 저장
링크 필드 : 다음 노드의 참조값을 저장- 헤드 : 연결리스트의 첫 노드에 대한 참조값을 갖고 있음
단순 연결리스트(Singly Linked List)
- 노드가 하나의 링크 필드에 의해 다음 노드와 연결되는 구조를 가진다.
- 헤드가 가장 앞의 노드를 가리키고, 링크 필드가 연속적으로 다음 노드를 가리킨다.
- 링크 필드가 Null인 노드가 연결리스트의 가장 마지막 노드이다.
원형 연결리스트(Circular Linked List)
- 원형 연결리스트는 단순 연결리스트와 비슷하고 다른 점은 head 포인터가 마지막 노드를 가리킨다.
- 원형 리스트는 head는 마지막 노드를, head의 link는 첫 노드를 가리키기 때문에 리스트의 처음이나 마지막에 노드를 삽입하는 연산이 편리하다는 장점이 있다.
다중 연결리스트(Doubly Linked List)
- 양쪽 방향으로 순회할 수 있도록 노드를 연결한 리스트
- 두 개의 링크필드와 한개의 데이터 필드로 구성
