Array와 LinkedList 비교

2019. 12. 1. 14:41

Array와 LinkedList의 비교

c++ 코드 포함

메모리 구조의 차이

Array

Array는 리스트에 포함되는 데이터의 메모리 위치들이 차례로 나열시킨 구조이다. 프로그래밍을 할 때 메모리(=주기억장치, 램, RAM)에 int 자료형을 담을 수 있는 공간 10개를 담은 배열(array)을 선언했다면, 아래 왼쪽 그림처럼 OS는 메모리에 10개의 int 자료형이 연속된 공간을 할당시키게 된다.

만약에, int와 같은 primitive 타입이 아닌, struct를 사용해서 새로운 타입 만들었다면, 이또한 연속된 공간으로 할당된다. 아래 오른쪽 코드처럼 struct 배열로 만들어서 프로그래밍을 하면 메모리에는 Element 구조단위로 10개가 연속된 공간으로 할당된다.

※ primitive type ? 프로그래밍을 할 때 언어에서 지원하는 가장 기본타입을 말하는 것으로 int, float, double, boolean 등이 될 수 있다. 참고로, java 언어에서는 int, double 말고도 이를 대신할 수 있는 Integer, Double 타입이 존재하긴 하지만, 이런 타입은 int와 같은 primitive 타입을 가지고 class화 시켜서 사용되는 타입이라고 해서 Wrapper Type이라고 따로 구분된다.

example) int array initialization

#include <iostream>
using namespace std;

int main() {
	int a[10] = {0,};
	return 0;
}

example) struct array initialization

#include <iostream>
using namespace std;

struct Element {
	int data = 0;
	int data2 = 0;
};
int main() {
	Element a[10];
	return 0;
}

LinkedList

LinkedList는 리스트에 포함되는 데이터의 메모리 위치들이 모두 떨어진 구조이다. 프로그래밍을 할 때, Array와 다르게 각 요소의 단위가 int, float 같은 primitive type는 될 수가 없다. 이러한 이유로 LinkedList에서는 int와 같은 primitive type을 사용한 다른 구조(struct or class)를 만들어서 사용하게 된다. 각 구조의 이름은 개발자 마음대로 부르지만 재구성한 구조를 보통 노드(Node)라고 부른다. 이 노드에는 반드시 들어가야하는 값이 있는데, 자기 자신과 동일한 구조의 변수 하나를 가지고 있어야 한다. 이 변수(=첫번째 노드)를 통해서만 다른 노드로 접근이 가능하기 때문이다.

LinkedList는 Array와는 다르게 보통 고정 크기를 가지도록 프로그래밍하지 않는다. 일반적으로 프로그램이 동작하면서 필요할 때마다 필요한 공간을 동적으로 추가시키거나 삭제시킬 수 있도록 프로그래밍 한다. 하지만, 이번 포스팅에서는 Array와의 차이를 이해하는 것이 목적이므로 고정된 크기를 가지는 것처럼 아래코드를 프로그래밍해봤다. 아래 그림처럼 코딩이 되었다면 OS는 메모리에 10개의 Node 자료형의 공간을 할당시키지만, 이 자료형은 메모리에 연속되지 않는다. 이것이 바로 메모리입장에서 Array와의 가장 큰 차이이다.

example) linked list initialization

#include <iostream>
using namespace std;

struct Node {
	Node* next;
	int data;
};
int main()
{
    	/* 10 크기의 링크드리스트 선언 & 초기화 */
	Node* head;
	for(int i=0; i<10; i++) {
		if(i==0)
			head = new Node({NULL, 0});
		else {
			Node* next = new Node({head, 0});
			head = next;
		}
	}
   	return 0;
}

특정 데이터 접근의 차이

Array

Array의 요소로 접근할 때는 인덱스(index)를 사용해서 바로 접근할 수 있다. 아래 코드처럼 10 크기를 가진는 배열의 4번째 요소의 값을 변경시키기 위해 4번째 인덱스로 바로 접근해서 해당 데이터를 수정할 수 있다.

example) int array modification

#include <iostream>
using namespace std;

int main() {
	int a[10] = {0,};
	a[4] = 7;
	return 0;
}

struct 자료형을 가지는 배열의 경우에도, struct 단위로 인덱스가 접근이 가능하다. 아래 코드는 재정의한 struct 구조 안에 있는 요소에 접근하는 코드이다.

example) struct array modification

#include <iostream>
using namespace std;

struct Element {
	int data = 0;
	int data2 = 0;
};
int main() {
	Element a[10];
	a[4].data = 7;
	a[4].data2 = 8;
	return 0;
}

LinkedList

LinkedList는 인덱스를 사용하지 않고, 반복문을 사용해서 각 노드로 접근해야 한다. 앞에서 말했듯이 LinkedList는 리스트의 첫번째 노드값을 통해서만 다른 노드로 접근이 가능하기 때문이다. 참고로, LinkedList에서는 첫번째 노드를 보통 head라고 부른다. 반복문을 사용해야 하기 때문에 Array와는 다르게 아래처럼 for문이나 while문이 등장하게 된다.

example) linked list modification

struct Node {
	Node* next;
	int data;
};
int main()
{
    	/* 10 크기의 링크드리스트 선언 & 초기화 */
	Node* head;
	for(int i=0; i<10; i++) {
		if(i==0)
			head = new Node({NULL, 0});
		else {
			Node* next = new Node({head, 0});
			head = next;
		}
	}

	/* 특정 위치의 노드 데이터를 접근 */
	int i=0;
	for(Node* current=head; current!=NULL; current=current->next) {
		if(i==4) 
			current->data = 7;
		i++;
	}
   	return 0;
}