[자료구조] 연결 리스트

연결 리스트의 필요성

일반적으로 배열을 사용하여 데이터를 순차적으로 저장하고, 나열할 수 있다.

하지만 배열을 사용하는 경우 메모리 공간이 불필요하게 낭비될 수 있음

 

배열 기반의 리스트

데이터를 순차적으로 저장하고 처리할 때는 배열 기반의 리스트를 이용

배열 기반의 리스트

#include <stdio.h>
#define INF 10000

int arr[INF];
int count = 0;

void addBack(int data)
{
	arr[count] = data;
	count++;
}

//!< 가장 앞쪽에 추가되는 data를 넣기 위해서 이미 추가되어 있는 데이터는 뒤쪽으로 하나씩 밀어줌
void addFirst(int data)
{
	for(int i=count; i >= 1; i--)
	{
		arr[i] = arr[i-1];
	}
	arr[0] = data;
	count++;
}

//!< 특정한 위치의 원소를 삭제
void removeAt( int index )
{
	for(int i=index;i < count-1;i++)
	{
		arr[i] = arr[i+1];
	}
	count--;
}

void show()
{
	for(int i=0; i< count; i++)
	{
		printf("%d", arr[i]);
	}
}

int main(void)
{
	addFirst(4);
	addFirst(5);
	addFirst(1);
	addFirst(7);
	addFirst(6);
	addFirst(8);
	show();
	system("pause");
	return 0;
}

결과
8 6 7 1 5 4

 

배열 기반 리스트의 특징

장점

•   배열로 만들었으므로 특정한 위치의 원소에 즉시 접근 가능

단점

• 데이터가 들어갈 공간을 미리 메모리에 할당해야 함
• 원하는 위치로의 삽입이나 삭제가 비효율적

 

연결 리스트

일반적으로 연결 리스트는 구조체와 포인터를 함께 사용해서 구현

연결 리스트는 리스트의 중간 지점에 노드를 추가하거나 삭제할 수 있어야 함

동적 할당을 이용하여 필요할 때마다 메모리 공간을 할당 받음

 

연결 리스트의 특징

장점

• 삽입과 삭제가 배열에 비해서 간단함

단점

• 배열과 다르게 특정 인덱스로 즉시 접근하지 못하며, 원소를 차례대로 검색해야 한다.
• 추가적인 포인터 변수가 사용되므로 메모리 공간이 낭비됨

 

삽입, 삭제 속도    :  배열 < 연결 리스트

인덱스 검색 속도  :  배열 > 연결 리스트