0x01.알고리즘(2):배열&연결 리스트

1. 배열(Array)

 

데이터를 하나의 순서로 나열한 것을 선형 리스트(linear list) 또는 열(sequence)라고 하는데, 주로 배열과 연결 리스트를 사용한다. 그 중에 배열은 메모리에 연속으로 데이터를 나열할 때 주로 사용하는데, 직접 접근에 용이하여 각 요소를 참조하는데 시간이 적게 걸린다는 장점이 있다.

 

int element[size];

 

하지만 연속된 특징 때문에 특정 열에 새로운 요소를 삽입할 경우, 그 장소를 비우기 위해 요소를 이동시켜야 되는 불편함이 있다.

 

장소 : p, 데이터 : val

 

void insert(int p, int val){

   int i;

   for(i=length; i>=p; i<<)

         elements[i+1]=element[i];

   length++;

   elements[p]=val;

}

 

열에 데이터를 삽입하기 위해서는 다음과 같이, 배열의 뒤에서부터 데이터를 하나씩 뒤로 이동시켜야 한다. 마찬가지로 삭제의 경우에도 요소를 앞으로 이동시킨다.

 

이런 특징 때문에 배열은 임의의 요소에 직접적으로 접근이 필요한 경우나 데이터를 나열하는 경우에 주로 사용된다.

 

 

 

2. 연결 리스크(linked list)

 

이 방식은 직접적인 참조는 비효율적이지만 데이터의 삽입 및 삭제가 빠르다는 장점이 있다.

 

 

데이터와 포인터로 구성된 각각의 기억장소를 노드(node)라고 하는데, 왼쪽엔 데이터 값, 오른쪽은 다음 노드를 나타내는 포인터 값이 들어간다. 마지막 노드의 포인터 값인 NULL은 리스트의 끝을 나타낸다. 보통 코딩을 할 때, 데이터 부분을 element, 포인터 부분을 next로 나타낸다.

 

아래는 노드를 구성하기 위한 프로토타입으로 사용되는 구조체이다.

 

struct node{

   int element;

   struct node * next;

} //노드의 구조체

 

listhead는 연결 리스트의 첫 노드를 나타내는 포인터로, 이 값을 통해 모든 노드를 참조할 수 있다.

 

struct node * listhead;

 

연결 리스트는 특정 요소를 참조하기 위해 첫 노드부터 순차대로 조사를 해야한다. 아래의 코드에서 start는 한 요소를 나타내는 포인터 값인데, while 조건문을 이용해 해당 요소까지 찾아가는 과정을 나타낸다.

 

ptr=start;

while(ptr){

   조건식(ptr->element);

   ptr=ptr->next;

}

 

아까 언급하였지만, 연결 리스트의 핵심은 쉬운 데이터 삽입과 삭제이다. 다음의 코드를 활용하면 노드와 노드 사이에 새로운 노드(데이터)를 삽입할 수 있다.

 

void insert(int val, struct node * previous){

   struct node *q;

   q=(struct node *)malloc(sizeof(struct node));

   q->element=val;

   q->next=previous->next;

   previous->next=q;

}

 

새로 삽입할 노드를 나타내는 포인터 값 q를 활용하여 다음 그림과 같이 노드를 삽입하였다.

 

 

하지만 젤 첫 부분에 노드를 삽입할 경우에는 listhead를 고려해야 하기 때문에 다음과 같은 방식으로 코딩을 하면 된다.

 

void inserthead(int val){

   struct node * q;

   q=(struct node *)malloc(sizeof(struct node));

   q->element=val;

   q->next=listhead;

   listhead=q;

}

 

새로 삽입된 노드의 다음 노드 포인터 값을 현재의 listhead 값으로 지정한 뒤에 listhead 값을 q의 포인터 값으로 변경하는 방법을 사용하였다.

 

다음의 코드는 연결리스트의 특정 노드의 삭제에 사용된다.

 

void delete(struct node * previous){

   struct node * q;

   q=previous->next;

   previous->next=q->next;

   free(q);

}

 

아래의 그림과 같이, 그 전 노드의 next 포인터 값을 삭제할 노드의 next 값으로 변경시켜 삭제할 노드를 건너뛰게 만들면 된다.

 

 

위와 같은 형태의 리스트를 선형 연결 리스트라고 한다. 이외에도 순환 연결 리스트, 양 방향 연결 리스트 등 다양한 종류가 있는데 여유가 있다면 한 번 찾아보는 것도 좋을 듯 하다.