순차 리스트: 배열 기반의 리스트
연결 리스트: 메모리 동적 할당을 기반으로 구현된 리스트
리스트 자료구조 기본 기능은 동일하지만 기능을 제공하는 특성에 차이가 있다.
리스트
- 나란히 저장된 자료구조로 중복된 데이터를 저장할 수 있다. 순서가 있고, 중복을 허용한다.
- 일렬로 늘어선 자료를 저장하기 때문에 선형 자료구조 라고 부른다.
배열과 비슷하게 볼 수 있지만, 배열과 전혀 다른 형태를 가지고 있다. 배열은 메모리가 연속적으로 위치해 있지만, 연결 리스트의 원소는 각자 메모리를 가지고 다음 원소를 가리키는 형식으로 구서현된다. 각 요소들을 노드 라고 부르며, c언어로 표현하자면 포인터로 다음 요소의 주소값을 가리키고, 자바로 표현하면 다음 요소를 참조하는 방식으로 연결된다.
연결리스트는 많이 사용하는 자료구조 중 하나로 많은 언어에서 라이브러리로 기본적으로 제공된다.
- 리스트 구현 방법
- 순차 리스트: 배열을 만들어 순서대로 저장하는 것이 가장 대표적인 방법이다.
- 장점: 랜덤 엑세스 가능
- 단점: 크기가 고정되어 삽입, 삭제 시 다수의 데이터를 옮겨야 한다 - 연결 리스트
- 장점: 길이의 제한이 없어 다른 데이터의 이동 없이 삽입, 삭제가 가능하다
- 단점: 랜덤 엑세스 불가능
- 순차 리스트: 배열을 만들어 순서대로 저장하는 것이 가장 대표적인 방법이다.
배열은 연속된 공간에 데이터가 저장되어 있고, 연결리스트는 순서에 맞추어 저장하지 않아도 다음 주소를 함께 가지고 있어 다음 요소로 연결할 수 있다. 연결 리스트는 장소에 관계 없이 삽입, 삭제가 가능하고 뒤의 주소값만 변경하면 쉽게 수정할 수 있다.
연결리스트는 물리적 순서와 논리적 순서가 동일하지 않아 데이터가 어디에 위치해 있는지 빠르게 알 수 없다. 인덱스로 순서는 구분할 수 있지만 배열처럼 완전한 식별자 역할을 하지 못하는 것이 단점이다. 하지만 프로그래머가 필요한 상황에 따라 메로리를 생성, 삭제할 수 있어 효율성이 증가된다.
노드
연결 리스트를 사용하다 보면 리스트의 각 요소를 노드라고 표현한다. 노드를 검색하면 '노드(node)는 컴퓨터 과학에 쓰이는 기초적인 단위' 라고 나오는데, 연결 리스트에서 말하는 노드는 하나의 데이터 필드와 그 이상의 링크 필드로 구성되는 것이다.
자바의 경우 List를 통해 ArrayList나 LinkedList를 생성하면 각 노드는 하나의 객체이다. c언어는 구조체를 사용하여 노드를 정의해 사용할 수 있다.
struct node {
char *data;
struct node *next;
}
typedef struct node Node;
단순 연결 리스트 (Singly Linked List)
한 방향으로 연결된 연결리스트
원형 연결 리스트 (Circular Linked List)
마지막 노드가 첫번재 노드를 연결해 하나의 원 모양이 되는 것
양방향 연결 리스트 (Doubly Linked List)
한 방향으로만 연결된 리스트가 아닌 양쪽으로 모두 연결된 리스트
'Knowledge > 자료구조' 카테고리의 다른 글
| [자료구조] 해시 테이블 (Hash Table) (0) | 2023.07.27 |
|---|---|
| [자료구조] 트리(Tree) (0) | 2023.07.06 |
| [자료구조] 스택(Stack) & 큐(Queue), 그리고 데크(Deque) (0) | 2023.02.06 |
| [자료구조] 그래프(Graph) (0) | 2023.02.02 |