리스트? (Linked List - 연결 리스트)
일반적으로 '리스트'는 연결 리스트(Linked List)를 뜻한다. 이후 Array List와 Vector를 추가로 설명하기 전까지 모든 설명은 연결 리스트(Linked List)에 대해 다룬다.
리스트는 배열처럼 데이터를 순서대로 표현하는 자료구조 중 하나인데, 구현 방법에 큰 차이가 있다.
배열은 메모리 상에 연속된 공간을 '미리 할당받고' 메모리상에 데이터를 순서대로 넣어 만든 자료구조이다.
리스트는 메모리 상에 데이터가 어디에 있던 신경쓰지 않는다. 'data = [12. 3. 11. -2]'를 배열과 리스트로 표현해보겠다.
위의 정갈하게 메모리상에 순서대로 들어가 있는 것이 배열, 아래쪽에 메모리상에 흩뿌려져 있는 것이 리스트이다. 이 때 배열, 리스트 모두 'data'라는 변수는 첫번째 데이터의 위치만을 가르키고 있다. 배열은 메모리 자체에 순서대로 들어가 있으므로 다음 데이터는 물론이고, n번째 데이터도 쉽게 알 수 있다. 하지만 현재 그림상으로는 리스트에서 첫번째 데이터인 '12'의 위치는 알 수 있지만 n번째 데이터는 커녕 바로 다음 데이터도 어디에 있는지 알 수 없다.
그럼 다음 데이터의 위치를 알 수 있도록 리스트 부분만 그림을 다시 그려보겠다.
이해를 돕기위해 각 위치의 메모리상 번지수도 써보았다. 기존 데이터를 1칸으로 표현할 때는 다음 위치를 알 수 없었다. 그래서 이번엔 2칸으로 하나는 데이터를, 하나는 다음 데이터가 있는 위치의 번지수를 써두었다. 이제 각 데이터를 순서대로 쫒아가면서 2번째 칸의 번지수를 보면 다음 데이터의 위치를 알 수 있으므로 모든 데이터를 위치를 알 수 있게 됬다!
하지만 배열로 표현할때와는 다르게 시작지점에서 n번째 데이터가 어디있는지는 바로바로 알 수 없게됬다. 메모리에 연속된 공간을 쓰지 않는 대신 빠르게 찾아갈 수 없게된 것이다. (TMI: 알고리즘이나 자료구조의 선택에는 항상 trade-off가 있다. DB에서도 인덱스를 걸면 검색이 빨라지는 대신 삽입 삭제가 느려지고, 인덱스를 만들어두기 위해 메모리 손실이 나는것과 마찬가지다.)
배열에 비해 리스트에서 탐색이 느려진 대신 얻게되는 trade-off를 확인하기 위해 CRUD를 같이 확인해보자.
1. Create - 기존에 없는 데이터를 새로 삽입하는 경우를 생각해보자.
1.1 시작은 아래와 같다. 3번째 데이터인 22 뒤에 데이터를 추가하려고 한다.
1.2 head에서 3번째 데이터의 위치를 알 수 없다. 따라서 리스트를 따라서 일단 3번째 데이터까지 찾아가야 한다.
1.3 그 다음 해당 위치 뒤에다가 데이터를 넣어주면 된다. 배열은 메모리상에 연속된 공간을 유지해야 해서 중간에 바로 넣을 수 없었고, 더 큰 새로운 배열을 만든 후에 다른것들을 다 복사하면서 넣을 수 있었다. 하지만 리스트는 메모리상 위치가 상관없으므로 서로간의 화살표만 조정하면 가능하다.
1.4 어..? 근데 이럼 배열이랑 똑같이 O(N)의 시간복잡도를 가지는거 아닌가? 맞다. 중간에 데이터를 삽입하는 경우라면 사실 배열이나 리스트나 비슷비슷하다. 다만 리스트는 일반적으로 맨 앞이나 맨 뒤에 데이터를 추가한다! 그리고 위는 head로 시작점만 표시했지만 보통 tail이라고 맨 뒤를 가르키는 변수도 존재한다. 따라서 한번만에 시작이나 끝 지점을 알 수 있고, 바로 데이터를 넣을 수 있다.
-- 따라서 리스트의 중간에 데이터를 넣을 경우 : O(N) / 맨 앞이나 맨 뒤에 넣을 경우 : O(1) - 일반적으로 이 경우가 많음
2. Read, Update - 데이터의 값을 확인하거나, 바꿔보자.
2.1 시작은 아래와 같다. 3번째 데이터를 확인하거나 바꿔보려면 마찬가지로 head에서 바로 알 수 있는 방법은 없으므로 순서대로 쭉 따라들어가서 값을 확인하거나 바꿔야 한다. 물론 이것도 맨 앞이나 맨 뒤의 데이터라면 바로바로 확인 가능하긴하지만 삽입과는 다르게 데이터 확인, 수정은 맨 앞이나 맨 뒤만 확인하지 않는다.
-- 따라서 맨앞이나 맨 뒤의 데이터를 확인하거나 바꿀 경우 : O(1) / 중간의 데이터를 확인하거나 바꿀 경우 : O(N) - 일반적으로 이 경우가 많음
3. Delete - 데이터를 삭제해보자.
3.1 3번째 데이터인 '22'를 삭제해보자. 마찬가지로 3번째 데이터까지 찾아간 후, 22대신 22 다음 데이터를 연결하면 된다. 22는 이후 Garbage Collector가 제거할 것이니 신경 안써도 된다.
-- 얘도 마찬가지로 중간의 데이터를 삭제할 경우 : O(N) / 맨앞이나 맨 뒤에 데이터를 확인하거나 바꿀 경우 : O(1) - 일반적으로 이 경우가 많음
배열은 언제쓰고 리스트는 언제쓸까?
결국 시간복잡도와 상황에 맞게 적절하게 사용하면 된다. 일반적으로 데이터의 추가, 삭제가 많은 경우 리스트를 사용하는 것이 효율이 좋다. 데이터가 자주 추가, 삭제 되지 않고, 읽고 수정하는 경우가 많을 때 배열을 사용하는 것이 효율이 좋다. 사실 명확하게 이 때는 이걸 써라! 라고 할 수 없다. 중요한건 배열과 리스트의 원리를 이해하고 현재의 로직에 적절한걸 쓰면 된다.(애초에 배열과 리스트는 기본중의 기본이다. 자료구조는 아직 엄청 많다.) 짜긴 짜는데 합당한 이유는 모르지만 아무튼 짜기 쉬우니 난 리스트로만 쓰겠어! 이런건 개발자에게 좋은 마인드가 아니라 생각한다.
LinkedList vs ArrayList vs Vector
위는 모두 연결 리스트에 대해 다루었다. 그런데 특히나 자바를 써본 사람들은 ArrayList와 LinkedList를 둘다 리스트 자료구조인 것 처럼 혼동한다. 그도 그럴것이 List<Integer> list = new ArrayList<>(); 처럼 마치 리스트 자료구조인냥 생각하도록 이름을 지어놨다. 자바에서 ArrayList는 배열을 Collection 프레임워크의 List 인터페이스에 맞춰 사용할 수 있도록 만들어둔 것 뿐이다. 다만 거기에 추가로 배열처럼 크기를 설정하지 않고 사용할 수 있으며 크기가 가변적이라는 추가 장단점이 붙었다. (메모리를 효율성 하락 : 단점, 배열이지만 크기 가변적 사용 : 장점)
기본 동작 원리 및 CRUD에 따른 효율성은 모두 배열과 동일하다. 이걸 이해하는게 매우 중요한게, 보통 자료구조에 대해 잘 모르고, 자바 자체도 초보인 사람들은 리스트를 처음 사용할 때 ArrayList와 LinkedList 둘 중 대충 아무꺼나 쓰고 한번 써봤으니깐 그걸로 앞으로 계속 써버린다.
당연히 LinkedList와 ArrayList의 CRUD 효율성은 매우 다르므로 아무꺼나 쓰면 매우 비효율적인 코드가 되버린다. 자바에서 ArrayList는 배열을 썼을 때 효율적으로 동잘할 로직을 수행하려고 하는데, 배열의 크기를 모를 때, 혹은 배열로 구현하기 귀찮을 때 어차피 메모리 크기 널널하면 대충 넣기 좋으니까 사용하는 것이다.(심지어 배열로 해도 그냥 미리 넉넉하게 만들거나, 다 차면 미리 한 2배정도로 늘려서 새로 만들어버리면 ArrayList와 동일하게 사용 가능하다.)
1. 자바에서 ArrayList가 어떻게 구현되어있는지 내부 코드를 까보자. 다음과 같이 Default Capacity (기본 배열 크기)를 설정해 둔 것을 확인할 수 있다. 맨 처음 크기 1개에서 시작하면 처음에 매번 크기 늘려야하니 10개정도로 잡아둔 것이다.
2. 다음과 같이 생성 시 원하는 기본 크기 설정도 가능하다. 정확히 어느정도 크긴지는 몰라도 대강 이정도 되겠네! 할 때 쓰면 된다.
3. 다음은 용량이 가득찬 경우 배열을 새로 할당받아 전부 복사하는 부분이다. 참고로 변수 n에 대해 n>>1은 모든 비트를 오른쪽으로 한 칸 옮긴것으로, n/2를 뜻한다. (n<<1은 같은 의미로 n*2를 뜻함) 따라서 자바에서는 기본적으로 배열의 크기를 1.5배씩 늘리면서 ArrayList를 구현한 것을 확인할 수 있다. (n + n/2 = 1.5n)
... 그러니 자바에서 LinkedList와 ArrayList를 혼동해서 비효율적으로 쓰지 말자.
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
public class Main {
private static void proc(List<Integer> list) {
long start = System.currentTimeMillis();
int sum = 0;
for (int i = 0; i < list.size(); i++)
sum += list.get(i);
System.out.println(sum);
System.out.println((System.currentTimeMillis() - start) / 1000f + " sec");
}
public static void main(String[] args) throws Exception {
// LinkedList
List<Integer> list = new LinkedList<>();
for (int i = 0; i < 100000; i++)
list.add(i);
proc(list);
// ArrayList
list = new ArrayList<>();
for (int i = 0; i < 100000; i++)
list.add(i);
proc(list);
}
}
(물론 위와 같이 순차적으로 차례대로 읽는다면 LinkedList도 Iterator로 돌리면 괜찮긴하다. 그냥 시간 차이를 보기위해 임의의 위치의 데이터를 읽어오는 경우를 표현한 것이다.)
그럼 Vector는 무엇이냐면 그게 위에서 설명한 자바의 ArrayList이다.
그러니까 일반적으로 List라고 하면 LinkedList를 뜻한다. 그리고 배열을 위처럼 미리 크기를 안정하고, 가득차면 몇배씩 늘리는 식으로 사용할 수 있도록 해둔 자료구조를 보통 Vector라고 부른다. 그러니 주언어가 자바인 사람이 ArrayList 어쩌구 하면 Vector로 알아들으면 된다.
... 근데 심지어 자바는 Vector도 있다 ㅡㅡ. 그럼 자바에서 Vector와 ArrayList의 차이점은 무엇이냐면 없다. 동일하다. 그냥 전체적으로 ArrayList가 더 우수한 성능을 보이니 ArrayList 쓰면 된다. 굳이 차이점이라면 Vector는 한 번에 하나의 Thread에서만 쓸 수 있고, ArrayList는 여러 Thread에서 쓸 수 있다. 딱히 Thread 여러개인 프로그램에서 서로 공유하지만 락 걸어둔 것 처럼 사용하고 싶은 경우 아니면 자바에서 Vector를 쓸 일은 딱히 없다.
정리하자면
1. 리스트라고 하면 LinkedList를 뜻한다.
2. 메모리에서 좀 손해를 보면 (trade-off) 배열이 가득 찼을 경우 미리 1.5배~2배 크기의 새로운 배열을 만드는 식으로 배열도 미리 크기를 설정하지 않고 가변크기'처럼' 사용할 수 있다. 효율성은 당연히 배열과 동일하다. 그걸 일반적으로 Vector라고 한다. 다만 자바에서는 그걸 추가로 ArrayList라고도 한다.
List 구현해보기
대부분의 언어에서는 리스트를 기본적으로 지원한다. 하지만 c처럼 기본적으로 지원안하는 경우도 있고, 기본형태로라도 자신이 현재 사용하는 주 언어로 한번씩 꼭! 짜보는 것이 좋다. 다음은 한번 자바와 c로 짜본 linked list 이다.
- 자바에서 제너릭에 상속, 구현까지 써가며 짜면 이해하기 힘들테니 아주 기본적인 형태의 Object 리스트를 짜봤다. 다만 추가로 위에서 설명했던 방식에서, 이전으로도 갈 수 있는 형태이다. 이걸 doubly linked list라고 부른다. 예시일 뿐 명확히 검증을 안해봐서 틀린 부분이 있을 수 있긴하다.
class Node {
Node prev;
Node next;
Object data;
public Node(Object data) { this.data = data; }
public Node() { this(null); }
}
class ListPrac {
private Node head;
private Node tail;
private int size;
public ListPrac() {
head = tail = null;
size = 0;
}
public int size() { return size; }
public boolean isEmpty() { return size == 0; }
public void add(Object data) { addLast(data); }
public void addFirst(Object data) {
Node node = new Node(data);
if (isEmpty()) {
head = tail = node;
} else {
node.next = head;
head.prev = node;
head = node;
}
size++;
}
public void addLast(Object data) {
Node node = new Node(data);
if (isEmpty()) {
head = tail = node;
} else {
node.prev = tail;
tail.next = node;
tail = node;
}
size++;
}
public void removeFirst() {
if (size <= 1) {
head = tail = null;
size = 0;
} else {
head = head.next;
head.prev = null;
size--;
}
}
public void removeLast() {
if (size <= 1) {
head = tail = null;
size = 0;
} else {
tail = tail.prev;
tail.next = null;
size--;
}
}
public Object getFirst() {
if (isEmpty())
return null;
return head.data;
}
public Object getLast() {
if (isEmpty())
return null;
return tail.data;
}
public Object get(int idx) {
if (idx+1 > size())
return null;
if (size/2 >= idx) {
Node iter = head;
while (--idx >= 0) {
iter = iter.next;
}
return iter.data;
} else {
Node iter = tail;
while (++idx < size()) {
iter = iter.prev;
}
return iter.data;
}
}
}
- 마찬가지로 C에서도 짜봤다. 다만 객체지향 개념을 좋아하니 C언어지만 객체지향이 좀 묻어나게 짜봤다. 리눅스 커널도 이런식으로 짜져있다. 좀 더 복잡하지만.
1. node.h
/**
* Node structure
* made by nahwasa
*/
#ifndef NODE_H_NAHWASA
#define NODE_H_NAHWASA
typedef struct node {
struct node* prev; // previous Node
struct node* next; // next Node
void* data; // node's data. it can be any data type
} node_t;
#endif2. list.h
/**
* Basic Linked List Header
* This list using node(node.h)
* made by nahwasa
*/
#ifndef BASIC_LIST_H_NAHWASA
#define BASIC_LIST_H_NAHWASA
#include"node.h"
typedef struct list_head {
node_t* head; // first Node
node_t* tail; // last Node
int size; // number of Nodes
struct list_operations* op; // list operations
} list_t;
struct list_operations {
int (*get_size)(list_t* l);
int (*is_empty)(list_t* l);
void (*insert_to_head)(list_t* l, void* data);
void (*insert_to_tail)(list_t* l, void* data);
void (*delete_head_node)(list_t* l);
void (*delete_tail_node)(list_t* l);
node_t* (*get_head_node)(list_t* l);
node_t* (*get_tail_node)(list_t* l);
void (*print)(list_t* l);
void (*destroy)(list_t* l);
void (*insert_to_before_node)(list_t* l, node_t* pos, void* data);
};
extern list_t* create_list();
#endif3. list.c
/**
* Basic Linked List
* made by nahwasa
*/
#include<stdio.h>
#include<stdlib.h>
#include"list.h"
list_t* create_list();
static void destroy(list_t* l);
static int get_size(list_t* l);
static int is_empty(list_t* l);
static void insert_to_head(list_t* l, void* data);
static void insert_to_tail(list_t* l, void* data);
static void delete_head_node(list_t* l);
static void delete_tail_node(list_t* l);
static void print(list_t* l);
static node_t* get_head_node(list_t* l);
static node_t* get_tail_node(list_t* l);
static void insert_to_before_node(list_t* l, node_t* pos, void* data);
/*
* Operations can be override
* Someone who want change operations, make own create_list function and change '&op' to another
*/
static struct list_operations op =
{
.get_size = get_size,
.is_empty = is_empty,
.insert_to_head = insert_to_head,
.insert_to_tail = insert_to_tail,
.delete_head_node = delete_head_node,
.delete_tail_node = delete_tail_node,
.print = print,
.get_head_node = get_head_node,
.get_tail_node = get_tail_node,
.destroy = destroy,
.insert_to_before_node = insert_to_before_node
};
/*
* create list object and return
*/
list_t* create_list()
{
list_t* l = (list_t*)malloc(sizeof(list_t));
l->op = &op;
l->head = l->tail = NULL;
l->size = 0;
return l;
}
/*
* c language don't provide the way to release memory
* so programmer must provide destroy function
*/
static void destroy(list_t* l)
{
node_t* p;
node_t* t;
if ( l->op->get_size(l) > 0 ) {
p = l->op->get_head_node(l);
while (p != NULL) {
t = p->next;
p->next = p->prev = p->data = NULL;
free(p);
p = t;
}
l->head = NULL;
l->tail = NULL;
l->size = 0;
free(l);
l = NULL;
}
}
/*
* return the number of Nodes
*/
static int get_size(list_t* l)
{
return l->size;
}
/*
* if list has no node, return true(1)
*/
static int is_empty(list_t* l)
{
return !l->op->get_size(l);
}
/*
* insert Node to first of list
*/
static void insert_to_head(list_t* l, void* data)
{
node_t* nd = (node_t*)malloc(sizeof(node_t));
if ( l->op->is_empty(l) ) { // when there's no node
nd->prev = nd->next = NULL;
nd->data = data;
l->head = l->tail = nd;
} else {
nd->prev = NULL;
nd->next = l->head;
nd->data = data;
l->head->prev = nd;
l->head = nd;
}
l->size++;
}
/*
* insert Node to last of list
*/
static void insert_to_tail(list_t* l, void* data)
{
node_t* nd = (node_t*)malloc(sizeof(node_t));
if ( l->op->is_empty(l) ) {
nd->prev = nd->next = NULL;
nd->data = data;
l->head = l->tail = nd;
} else {
nd->next = NULL;
nd->prev = l->tail;
nd->data = data;
(l->tail)->next = nd;
l->tail = nd;
}
l->size++;
}
/*
* insert new Node before 'pos' Node
*/
static void insert_to_before_node(list_t* l, node_t* pos, void* data)
{
node_t* nd = (node_t*)malloc(sizeof(node_t));
if ( l->head == pos ) {
l->op->insert_to_head(l, data);
return;
}
if ( l->op->is_empty(l) ) {
nd->prev = nd->next = NULL;
nd->data = data;
l->head = l->tail = nd;
} else {
nd->data = data;
pos->prev->next = nd;
nd->next = pos;
nd->prev = pos->prev;
pos->prev = nd;
}
l->size++;
}
/*
* delete first Node
*/
static void delete_head_node(list_t* l)
{
if ( l->op->get_size(l) <= 1 ) { // when there's No Node or only one Node
l->head = l->tail = NULL;
l->size = 0;
} else {
l->head = l->head->next;
l->head->prev = NULL;
l->size--;
}
}
/*
* delete last Node
*/
static void delete_tail_node(list_t* l)
{
if (l->op->get_size(l) <= 1) {
l->head = l->tail = NULL;
l->size = 0;
} else {
l->tail = l->tail->prev;
l->tail->next = NULL;
l->size--;
}
}
/*
* print the Nodes
*/
static void print(list_t* l)
{
node_t* p = l->op->get_head_node(l);
while (p != NULL) {
printf("%s\n", (char*)p->data);
p = p->next;
}
}
static node_t* get_head_node(list_t* l)
{
return l->head;
}
static node_t* get_tail_node(list_t* l)
{
return l->tail;
}
끝.
'CS > Data structures' 카테고리의 다른 글
| [자료구조] C언어 - 다항식(polynomial) 구현 - 객체지향 (0) | 2022.04.09 |
|---|---|
| [자료구조] C언어 - 이중 연결 리스트(doubly linked list) 구현 - 객체지향 (0) | 2022.04.09 |
| 이분 그래프 (bipartite graph) (0) | 2022.03.23 |
| 자료구조 큐, 스택, 덱 (Queue, Stack, Deque) (0) | 2021.10.11 |
| 자료구조 배열 기본 (0) | 2021.09.22 |
댓글