2014년 모두들 어떤 목적과 계획을 갖고 살고 계신지요? 저는 올 한해 “Go to the Base”를 목표로 여러 계획을 세웠는데요. 그 중 하나가 과거 5년 동안 저를 되 돌아 보고 부족했던 기본 지식을 탄탄히 하는 것이었습니다. 그 중 하나가 자료구조와 알고리즘 이었습니다. 자료구조라 하니 어떻게 시작해야 할까 막막했는데요, 마침 KOSTA에서 1주일 일정으로 자료구조 강의가 개설되어 좋은 기회다 싶어 수강하게 되었습니다. 수강 후 그간 프로젝트 경험에 비추어 느낀 점을 여러분과 공유하려 합니다.
LinkedList에 대하여
우리의 주 활동 무대인 JAVA에는 다양한 자료구조가 JCF(Java Collection Framework)라는 프레임워크로 제공되고 있습니다. 매일매일 우리는 JCF를 이용해 이런 다양한 자료구조를 손쉽게 사용하고 있는데요. 그래서 인지 각 자료구조가 어떻게 구현되고 어떻게 동작하는 지에 관해서는 조금은 등한시 하게 되는 것 같습니다. 이번에는 이런 자료구조들을 살펴보는 시간을 가져 보려고 합니다. 그 중 우리가 같이 살펴보려고 하는 자료구조는 LinkedList라는 자료구조입니다.
LinkedList의 계층구조와 특징
JCF계층 구조를 보면 LinkedList는 ArrayList와는 달리 List 인터페이스를 구현한 AbstractList를 상속하지 않고 AbstractSequentialList를 상속하고 있습니다. ArrayList는 데이터들이 순서대로 쭉 늘어선 배열의 형식을 취하고 있는 반면 LinkedList는 순서대로 늘어선 것이 아니라 자료의 주소 값으로 서로 연결되어 있는 구조를 하고 있습니다. 그림으로 보면 다음과 같습니다.
그럼 단순히 구조에서만 차이가 있을까요? 아닙니다. LinkedList는 ArrayList와 비교하여 여러가지 장점을 지니고 있습니다. LinkedList는 몇 개의 참조자만 바꿈으로써 새로운 자료의 삽입이나 기존 자료의 삭제를 위치에 관계없이 빠른 시간안에 수행 할 수 있습니다. ArrayList 같은 경우는 O(N)만큼의 연산 속도가 걸리기 때문에 자료의 최대 개수에 영향을 받지만, LinkedList는 그런 제약을 받지 않습니다. 또한 LinkedList는 무한 개수의 자료를 삽입할 수 있는 반면 (메모리의 용량이 무한정하다고 가정할 때), ArrayList는 크기가 한정되어 있기 때문에 결국 포화 상태에 이르게 됩니다. ArrayList의 크기를 재조정하는 연산을 수행하여 크기를 늘릴 수도 있지만, 상당한 연산량이 요구됩니다.
그럼 ArrayList에서의 삽입/삭제과정을 살펴보겠습니다.
이와 비교해서 LinkedList의 삽입/삭제 과정은 어떨까요? 한번 보도록 하겠습니다.
위 그림을 보면 아시겠지만 앞서 설명 드렸던 내용에 비추어 설명해 보면, ArrayList는 사이즈가 고정되어 있기 때문에 삽입 시 사이즈를 늘려주는 연산이 추가되어야 하고 삭제 시에는 순차적인 인덱스 구조로 인해서 삭제된 빈 인덱스를 채워야 하기때문에 채워주는 연산이 추가 되어야 했습니다. 이런 부가적인 연산은 시스템의 성능 저하로 이어져 삽입 / 삭제가 빈번하게 발생하는 프로세스의 경우 치명적이라 할 수 있겠습니다. 그리고 자료들이 지속적으로 삭제되는 과정에서 ArrayList에서는 그 공간 만큼 낭비되는 메모리가 많아지게 됩니다. 하지만 LinkedList는 이러한 문제를 연결형태로 해결하여 ArrayList에서 뒤로 밀거나 채우는 작업 없이 단지 주소만 서로 연결시켜 주면 되기 때문에 추가/삭제가 ArrayList보다 빠르고 용이 합니다. 따라서 이렇게 삽입 / 삭제가 빈번하게 발생하는 프로세스의 경우 LinkedList를 사용하여 시스템을 구현 하는것이 바람직하다 할 수 있겠습니다.
하지만, LinkedList의 단점도 존재합니다. ArrayList에서는 무작위 접근(random access)이 가능하지만, LinkedList에서는 순차접근(sequential access) 만이 가능합니다. 특히, (앞으로 우리가 구현하게 될) 단순 LinkedList는 단방향성을 갖고 있기 때문에 인덱스를 이용하여 자료를 검색하는 애플리케이션에는 적합하지 않습니다. 사실 순차 접근도 참조의 지역성(locality of reference: 전산 이론중의 하나로 한번 참조한 데이터는 다시 참조될 가능성이 높고 참조된 데이터 주변의 데이터 역시 같이 참조될 가능성이 높다는 이론입니다.) 때문에 LinkedList 보다는 ArrayList가 훨씬 빠릅니다. n개의 자료를 저장할 때, ArrayList는 자료들을 하나의 연속적인 묶음으로 묶어 자료를 저장하는 반면, LinkedList는 자료들을 저장 공간에 불연속적인 단위로 저장하게 됩니다. 그렇기 때문에 LinkedList는 메모리 이곳저곳에 산재해 저장되어 있는 노드들을 접근하는데 ArrayList보다는 긴 지연 시간이 소모됩니다. LinkedList의 또 다른 단점은 참조자를 위해 추가적인 메모리를 할당해야 하는 점입니다. 자료들의 크기가 작은 리스트의 경우 참조자를 위한 추가 적인 메모리할당은 비실용적일 수 있습니다. 정리하면 ArrayList와 비교한 LinkedList의 장/단점은 다음과 같습니다.
| 장점 | 단점 |
|---|---|
| 자료의 삽입과 삭제가 용이하다. | 포인터의 사용으로 인해 저장 공간의 낭비가 있다. |
| 리스트 내에서 자료의 이동이 필요하지 않다. | 알고리즘이 복잡하다. |
| 사용 후 기억 장소의 재사용이 가능하다. | 특정 자료의 탐색 시간이 많이 소요된다. |
| 연속적인 기억 장소의 할당이 필요하지 않다. |
ArrayList와 LinkedList의 비교 성능은 아래 표와 같습니다.
| ArrayList | LinkedList | |
|---|---|---|
| Indexing | Θ(1) | Θ(n) |
| Insert/delete at beginning | Θ(n) | Θ(1) |
| Insert/delete at end | Θ(1) | Θ(n)-last element is unknown Θ(1)-last element is known |
| Insert/delete in middle | Θ(n) | search time + Θ(1) |
| Wasted space (average) | Θ(n) | Θ(n) |
ArrayList와 LinkedList의 구현
이번엔 위 특성을 바탕으로 ArrayList와 LinkedList를 직접 비교하여 구현해보고 이를 이용하여 데이터를 추가하고 조회하여 출력해보는 시간을 갖도록 하겠습니다. 참고로 Java에서 구현되어 제공되고 있는 LinkedList는 방향성이 양쪽으로 존재하는 이중LinkedList(double-ended linked-list)로 구현 되어 있습니다. 하지만 여기서는 이해를 돕기위한 취지로 한방향성만 갖는 간단연결리스트로 구현해 보도록 하겠습니다.
먼저 ArrayList를 구현 해 보도록 하겠습니다. 구현은 다음과 같습니다.
package list;
public class MyArrayList {
final static int MAX_SIZE = 100;
private int[] data;
int length;
public MyArrayList() {
super();
this.length = 0;
data = new int[MAX_SIZE];
}
public MyArrayList(int size){
this.length = 0;
data = new int[size];
}
/**
* 배열의 마지막에 데이터를 추가한다.
* @param data
*/
public void add(int data){
int size = this.data.length;
//현재 배열의 길이와 사이즈가 같으면 사이즈를 증가시켜 새로운 배열에 복사한다.
if(this.length == size){
copyArray(data, size);
} else {
this.data[this.length] = data;
}
//
this.length++;
}
/**
* 배열의 특정인덱스에 데이터를 추가한다.
* @param data
*/
public void add(int index, int data){
int size = this.data.length;
//현재 배열의 길이와 사이즈가 같으면 사이즈를 증가시켜 새로운 배열에 복사한다.
if(this.length == size){
copyArrayWithIndex(index, data, size);
} else {
//배열의 인덱스를 중심으로 뒤로 한칸씩 이동한다.
for(int i = this.length-1; i > index-1; i--){
this.data[i+1] = this.data[i];
}
this.data[index-1] = data;
}
//
this.length++;
}
/**
* 배열의 마지막 데이터 삭제
*/
public void remove(){
if(this.length == 0) { throw new ArrayIndexOutOfBoundsException(); }
this.data[this.length-1] = 0;
this.length--;
}
/**
* 특정 인덱스의 데이터를 삭제한다.
* @param index
*/
public void remove(int index){
if(this.length == 0) { throw new ArrayIndexOutOfBoundsException(); }
this.data[index -1] = 0;
//삭제된 이후 데이터로 차례대로 채운다.
for(int i = index - 1; i < this.length-1; i++){
this.data[i] = this.data[i+1];
}
this.length--;
}
/**
* 배열복사메소드
* @param data
* @param size
*/
private void copyArray(int data, int size) {
int newSize = size + 1;
int[] newArray = new int[newSize];
newArray[newSize-1] = data;
for(int i = 0; i < size; i++){
newArray[i] = this.data[i];
}
this.data = new int[newSize];
for(int i = 0; i < newArray.length; i++){
this.data[i] = newArray[i];
}
}
/**
* 특정 인덱스 배열복사메소드
* @param index
* @param data
* @param size
*/
private void copyArrayWithIndex(int index, int data, int size) {
int newSize = size + 1;
int[] newArray = new int[newSize];
newArray[index-1] = data;
//인덱스를 중심으로 이전데이터 복사
for(int i = 0; i < index-1; i++){
newArray[i] = this.data[i];
}
//인덱스를 중심으로 이후데이터 복사
for(int i = newSize-1; i > index-1; i--){
newArray[i] = this.data[i-1];
}
this.data = new int[newSize];
for(int i = 0; i < newArray.length; i++){
this.data[i] = newArray[i];
}
}
public int get(int index){
return this.data[index];
}
}
구현된 MyArrayList입니다. 리스트는 int형의 배열로 이루어져있고, 리스트의 크기를 나타내는 length라는 변수와 추가메소드 2개, 삭제메소드 2개로 구성되어 있습니다. 구현 코드를 보시면 아시겠지만 LinkedList와는 달리 Node라는 별도의 객체가 없습니다. 그리고 추가 삭제시 사이즈가 꽉차면 리스트의 사이즈를 동적으로 증가 시켜주는 연산이 포함되어있음을 알 수 있습니다. copyArray 메소드와 copyArrayWithIndex 메소드가 바로 그것 인데요, 실제 Java에서 제공하는 ArrayList를 보면 Arrays.copyOf(elementData, newCapacity)를 이용하여 배열의 크기를 동적으로 늘리고 System.arraycopy()를 이용하여 리스트를 복사하고 있습니다. 이렇게 하여 ArrayList를 구현해 보았고, 다음은 LinkedList를 구현해 보겠습니다. ArrayList와는 다른 구조를 취하고 있기 때문에 이를 구현하기 위해서는 먼저 LinkedList에 필요한 사항들에 대해서 정리를 해야겠습니다.
- 데이터가 없는 시작 노드를 가진다. 이 노드는 처음 노드가 추가 될 때 다음의 노드를 가리키기만 한다.
- 각 노드는 재귀적으로 다음의 노드를 가지고 있다.
- 각 노드는 데이터를 가지고 있다.
- 추가, 삭제 등 기능이 있다.
- 구현하게될 노드의 구조는 다음의 그림과 같습니다.
package list;
public class MyLinkedList {
private Node head;
private int size;
public MyLinkedList(){
head = null;
size = 0;
}
/**
* 특정 인덱스에 새로운 노드를 추가한다.
* @param index
* @param newNode
*/
public void add(int index, Node newNode){
//첫번째 노드인 경우
Node nextNode = null;
if(index == 0 ){
if(this.head == null){
this.head = new Node();
this.head.setNext(newNode);
} else{
nextNode = this.head.getNext();
newNode.setNext(nextNode);
this.head.setNext(newNode);
}
} else {
//첫번째 노드가 아닌경우
if( index < 0 || index > this.size-1 ) {throw new IndexOutOfBoundsException();}
Node p = this.head;
for(int i = 0; i < index-1; i++){
p = p.getNext();
if(index < this.size) nextNode = p.getNext();
}
if(nextNode != null) newNode.setNext(nextNode);
p.setNext(newNode);
}
this.size++;
}
/**
* 마지막노드로 새로운 노드를 추가한다.
* @param index
* @param newNode
*/
public void add(Node newNode){
//첫번째 노드인 경우
if(this.head == null){
this.head = new Node();
this.head.setNext(newNode);
} else {
Node p = this.head;
for(int i = 0; i < this.size; i++){
p = p.getNext();
}
p.setNext(newNode);
}
this.size++;
}
/**
* 해당 index의 노드를 삭제한다.
* @param index
* @param node
*/
public void remove(int index){
//
Node headNode = this.head;
if(headNode == null){System.out.println("삭제할 데이터가 없습니다.");}
Node p = headNode;
for(int i = 0; i < index-1; i++){
p = p.getNext();
}
p.setNext(p.getNext().getNext());
this.size--;
//
}
/**
* 마지막 노드를 리턴한다.
* @return
*/
public Node get(){
if(this.head == null) throw new IndexOutOfBoundsException();
Node p = head;
for(int i = 0; i < this.size; i++){
p = p.getNext();
}
return p;
}
public void printList(){
System.out.println("<<LinkedList Data출력>>");
if(this.head != null){
Node p = this.head;
for(int i = 0; i < size; i++){
p = p.getNext();
if(p != null) System.out.print(p.getData()+", ");
}
}
}
/**
* @return the size
*/
public int getSize() {
return size;
}
/**
* @param size the size to set
*/
public void setSize(int size) {
this.size = size;
}
}
package list;
public class Node {
private Node next;
private int data;
/**
* @return the next
*/
public Node getNext() {
return next;
}
/**
* @param next the next to set
*/
public void setNext(Node next) {
this.next = next;
}
/**
* @return the data
*/
public int getData() {
return data;
}
/**
* @param data the data to set
*/
public void setData(int data) {
this.data = data;
}
}
자, 간단한 MyLinkedList가 만들어 졌습니다. 이제 간단한 테스트를 진행해 보겠는데요.
- 만들어진 MyArrayList와 MyLinkedList에 임의의 배열을 생성하여 추가합니다.
- 추가한 데이터를 출력해보고, MyArrayList와 MyLinkedList의 사이즈도 확인합니다.
- MyArrayList와 MyLinkedList에 새로운 데이터도 추가해보고, 특정위치에 새로운 데이터도 추가해 봅니다.
- 이렇게 추가 된 데이터를 다시 출력해서 확인 합니다.
package list;
public class LinkedListTest {
public static void main(String[] args) {
int[] array = {66, 33, 99, 55, 88, 22, 24, 77};
//MyArrayList테스트
System.out.println("<<<<<<<<<<<< MyArrayList테스트 >>>>>>>>>>>>>");
MyArrayList myArrayList = new MyArrayList(array.length);
for(int i = 0; i < array.length; i++){
myArrayList.add(array[i]);
}
myArrayList.add(18);
System.out.println("마지막 인덱스에 '18'추가");
for(int i = 0; i < myArrayList.length; i++){
System.out.print(myArrayList.get(i) + ", ");
}
System.out.println("");
System.out.println("MyArrayList의 사이즈:"+ myArrayList.length);
System.out.println("");
System.out.println("");
myArrayList.add(3, 20);
System.out.println("3번째 인덱스에 '20'추가");
for(int i = 0; i < myArrayList.length; i++){
System.out.print(myArrayList.get(i) + ", ");
}
System.out.println("");
System.out.println("MyArrayList의 사이즈:"+ myArrayList.length);
System.out.println("");
System.out.println("");
myArrayList.remove();
System.out.println("마지막 인덱스 삭제");
for(int i = 0; i < myArrayList.length; i++){
System.out.print(myArrayList.get(i) + ", ");
}
System.out.println("");
System.out.println("MyArrayList의 사이즈:"+ myArrayList.length);
System.out.println("");
System.out.println("");
myArrayList.remove(3);
System.out.println("3번째 인덱스 삭제");
for(int i = 0; i < myArrayList.length; i++){
System.out.print(myArrayList.get(i) + ", ");
}
System.out.println("");
System.out.println("MyArrayList의 사이즈:"+ myArrayList.length);
System.out.println("");
System.out.println("");
System.out.println("<<<<<<<<<<<< MyLinkedList테스트 >>>>>>>>>>>>>");
MyLinkedList myLinkedList = new MyLinkedList();
Node node = null;
printData(array);
System.out.println("");
for(int i = 0; i < array.length; i++){
node = new Node();
node.setData(array[i]);
myLinkedList.add(node);
}
System.out.println("LinkedList size : " + myLinkedList.getSize());
System.out.println("");
Node lastNode = myLinkedList.get();
System.out.println("Last Node data : "+ lastNode.getData());
System.out.println("");
Node addNode = new Node();
addNode.setData(100);
myLinkedList.add(3, addNode);
System.out.println("3번째 인덱스에 새로운 노드를 추가한다.");
myLinkedList.printList();
System.out.println("");
System.out.println("");
System.out.println("3번째 인덱스의 노드를 삭제한다.");
myLinkedList.remove(3);
myLinkedList.printList();
}
public static void printData(int[] data){
System.out.println("<<원 데이터 출력>>");
for(int i = 0; i < data.length; i++){
System.out.print(data[i] +", ");
}
System.out.println("");
}
}
결과화면은 다음과 같습니다.
마치며
1주일 간의 시간으로 그 많은 자료구조와 복잡한 알고리즘이 깔끔히 이해가 되진 않았습니다. 다만 그간 학습하고 고민했던 시간만큼은 헛되지 않게 해야겠다는 생각을 했습니다.자료구조와 알고리즘이 프로그래밍의 기반기술임에도 불구하고 그동안 너무 소홀히 하지않았나 생각 합니다. 그리고 평소에 Java API에서 기본으로 제공 된다는 이유로 깊은 생각 없이 사용했던 자신을 반성합니다. 앞으로는 이 자료구조를 왜 사용 해야 하는지 다른 대안은 없는지 고민하고, 한번 더 생각하는 습관을 키워야겠습니다. 소프트웨어 개발자라는 명함을 내밀기가 쉽지 않네요. 감사합니다.
참조자료
- DataStructure with Java Language 송주석/서성훈 저, 사이텍미디어
- KOSTA 자료구조(2014. 02, 이희두 강사) 강의 자료
타이틀 이미지는 독일 튀링엔주 바이마르의 “안나 아말리아 공비(公妃) 도서관”(Herzogin Anna Amalia Bibliothek)으로 요한 볼프강 폰 괴테가 유명한 후원자중 한 명이라고 합니다. 세계에서 가장 많은 파우스트 컬렉션을 소장하고 있으나, 2004년 화재 사고로 진귀한 장서들이 소실된 가슴 아픈 역사가 있는 곳입니다.
