[자료구조] 리스트(List)

리스트는 자주 사용되는 자료구조 중에 하나다. 

노드를 생성하고, 이를 포인터를 이용해 연결 시켜준다고 해서 연결리스트(Linked List)라고 한다. 배열만큼이나 자주 사용되는 자료구조다.

배열과 링크드 리스트는 순서대로 데이터를 나열한다는 공통점이 있지만 차이점과 각각의 장점이 있기 때문에 필요에 따라 사용한다.

[배열]

배열은 인덱스 번호를 가지고 있다. 때문에 원하는 데이터의 위치를 알고 있다면 빠르게 참조할 수 있다.

결과적으로 N번 째 요소의 참조를 자주 해야 하는 경우에는 배열을 사용한다. 배열의 인덱스를 통해 빠르게 원하는 데이터를 사용할 수 있다는 장점을 지닌다.

[리스트]

리스트는 중간에 데이터를 삽입해야 하거나, 삭제해야하는 경우에 용이하다.

보이는 것처럼 새로운 노드를 생성하고 포인터를 이용해 중간에 넣을 수 있다는 장점이 있다. 

배열이라면 배열을 왼쪽이나 오른쪽으로 데이터를 밀어서 배열의 중간 인덱스에 공백이 되는 일이 없도록 구현해야하므로 이런 경우는 리스트가 더 간편하다.

결과적으로 수정, 삭제가 배열보다 빠르기 때문에 구현할 때 수정과 삭제가 자주 요구된다면 리스트를 사용하는 것이 좋다. 

그리고 실제로 배열을 선언할 때와 리스트의 노드가 생성될 때 메모리 주소가 할당되는 것이 다르다. 배열은 규칙적인 크기가 증가된(자료형에 따른) 메모리 주소로 할당된다. 이에 반해 리스트는 임의의 메모리 주소로 할당된다.

 

다음 예시를 만들어 보았다.

[배열]

배열 int형 자료형으로 선언을 해서 1번 인덱스부터 10 인덱스까지 출력해보았다. 자료형이 int형이기 때문에 4씩 증가하는 것을 볼 수 있다.

<소스코드>

	#include <cstdio>
	#include <iostream>
	using namespace std;
	int main() {
	int arr[100] = { 0, };
	for (int i = 1; i <= 10; i++) {
	arr[i] = i;
	printf("%d\n", &arr[i]);
	}
	}

view rawArray_Memory_Test.cpp hosted with ❤ by GitHub

<결과창>

[리스트]

단일 연결리스트 구조에서 데이터를 삽입하는 함수를 호출해 새로운 노드를 생성하고, 노드 머리에 새로운 노드를 연결시켜 주는 것을 구현했다.

그 때의 newNode의 데이터의 메모리 주소를 출력해 보았다. 결과창처럼 임의의 메모리 주소에 할당 된다는 것을 알 수 있다.

<소스코드>

	#include <cstdio>
	#include <iostream>
	using namespace std;
	template <typename T>
	class Node {
	public:
	T data;
	Node *next;
	Node(){}
	Node(T data):data(data) {
	this->next = NULL;
	}
	Node *head = NULL;
	void addNode(T data) {
	Node *newNode = new Node(data); //새로운 노드생성
	if (head == NULL) {
	head = newNode;
	}
	else {
	newNode->next = head;
	head = newNode;
	}
	printf("%d\n", &newNode->data);
	}
	};
	int main() {
	Node <int> data;
	for (int i = 1; i <= 10; i++) {
	data.addNode(i);
	}
	}

view rawLinkedList_Memory_Test.cpp hosted with ❤ by GitHub

<결과창>

연결리스트 종류에는 대표적으로 세가지가 있다.

1. 단일 연결리스트(Singly Linked List)

2. 이중 연결리스트(Doubly Linked List)

3. 원형 연결리스트(Circular Linked List)

다음 포스트에는  여기 세 가지에 대해 정리해보려고 한다. 평소에 내가 자주 사용하는 것은 단일연결리스트지만 글을 올리면서 다른 리스트도 공부해보고, 쓰임에 따라 어떠한 리스트를 쓰는 것이 좋은 지 알아보려 한다.

출처 : http://meylady.tistory.com