[자료구조] 연결리스트 : 도입

학습 목표

연결 리스트의 정의를 설명할 수 있다.

 

1. 데이터 구조

기본적인 포인터 구조만 이용해서 메모리를 관리하기에는 다소 번거로울 때가 많다.

데이터 구조는 컴퓨터 메모리를 더 효율적으로 관리하기 위해 새로 정의하는 구조체이다.

쉽게 기억하기 위해, 일종의 메모리 레이아웃 또는 메모리 지도라고 생각하자.

2. 연결 리스트

배열에서는 각 인덱스의 값이 메모리상에서 연이어 저장되어 있다.
하지만 다음 인덱스의 값이 메모리상에서 멀리 떨어져 있다면 안되는 걸까?

각 인덱스 값이 메모리상에 여러 군데 나뉘어져 있다고해도 자기 바로 뒤에 오는 값의 메모리 주소만 기억하고 있다면 그 값을 연이어서 읽어들일 수 있다.

이것을 연결 리스트라고 한다.

• 크기가 3인 연결 리스트 이다.
• 이 연결리스트는 각 인덱스가 메모리 주소에서 자기 값이랑 함께 바로 다음에 오는 값의 주소(포인터)를 저장한다.
• 연결 리스트의 첫 번째 값인 1은 2의 메모리 주소를 저장하고 있고, 두 번째 값인 2는 3의 메모리 주소를 저장하고 있다.
• 3은 다음에 오는 값이 없기 때문에 NULL을 주소 값으로 저장한다.
  
  

2.1 구조체

typedef struct node
{
    int number;
    struct node *next;
}
node;

• node라는 이름의 구조체에는 number와 *next 필드가 정의되어 있다.
• number는 각 node가 가지는 값, 위의 그림에 나온 크기가 3인 연결리스트에서 1, 2, 3을 말하고, *next는 다음 node를 가리키는 포인터이다.
  
  

3. 배열과 비교했을 때

• 연결리스트는 다음 값의 주소를 저장하기 때문에 배열과 달리 메모리 상에서 서로 물리적으로 떨어져 있어도 연결이 가능하다.
• 배열은 고정된 갯수만 저장할 수 있는데, 연결 리스트는 필요할 때마다 데이터를 추가, 삭제할 수 있다.
• 연결리스트는 위치를 나타낼 때 인덱스 사용이 불가능하다.
• 원하는 값을 찾을 때까지 포인터를 통해서 노드를 탐색해 나가야하기 때문에 시간이 오래 걸린다.