선형 자료구조인 리스트는 그 종류가 다양하다. 그 중에서 가장 대표적인 배열리스트(array list), 단순연결리스트(linked list), 이중연결리스트(doubly linked list)에 대해서 정리해보았다.
배열리스트는 배열을 이용한 리스트형 자료구조로, 자바에서 지원해주는 클래스인 import java.util.ArrayList; 를 사용하면 된다. 구현이 매우 간단하며 탐색 시 인덱스를 이용할 수 있어서 탐색속도가 월등하다는 장점이 있다. 따라서 탐색, 정렬을 자주 하는 경우엔 배열리스트를 사용한다. 해당 클래스에는 아래와 같은 메소드들이 저장되어 있다. 참고로 이 메소드들을 이용해서 Deque를 구현할 수 있다.
| 메소드 | 설명 |
| int size() | 배열의 크기 러틴 |
| boolean isEmpty() | 배열이 비었는지 아닌지 여부 리턴 |
| Object get(int i) | i번째 index의 element 리턴 |
| Object set(int i, Object e) | i번째 index의 element를 e로 교체 후 교체 전 값 리턴 |
| void add(int i, Object e) | i번째 index에 element e 삽입(첫번째 인자 생략하면 배열의 마지막에 삽입) |
| Object remove(int i) | i번째 index의 element 삭제 후 삭제된 값 리턴 |
| boolean addAll(Collection c) | Collection 객체에 있는 element들을 리스트에 모두 추가 |
아래는 위 메소드들을 test한 예제이다.
ArrayList arrList = new ArrayList();
if(arrList.isEmpty() == true){
System.out.println("배열이 비어있습니다");
arrList.add("a");
arrList.add("b");
arrList.add("c");
arrList.add("d");
arrList.add("e");
}
else{
System.out.println("배열에 저장된 값이 있습니다.");
}
arrList.get(0);
arrList.remove(0);
arrList.set(1,2);
System.out.println(arrList);
System.out.println(arrList.size());배열은 한번 크기를 정하면 끝인 성질을 가지고 있어서 주의를 기울이지 않으면 IndexOutOfBoundException 문구를 자주 보게 될 것이다. 그러나 growable array라는 특이한 배열을 사용하면 별다른 조치 없이도 배열의 범위를 신경쓰지 않아도 된다. growable array는 add연산 중 range overflow가 발생하면 Exception을 throw하지 않고 더 큰 배열로 바꿔주는 배열이다. 교체 방법은 2가지가 있다. 하나는 incremental solution으로, 사용자가 지정한 상수 c만큼 배열의 크기를 증가시키는 것이다. 또 하나는 doubling solution으로, 이전 배열의 크기를 2배한 새로운 배열을 생성해 리스트의 값들을 복사/붙여넣기를 한 후 원래 배열로 바꿔치기하는 것이다. 물론 구현은 일반 배열리스트에 비하면 까다롭다.
단순연결리스트는 element들을 일방향의 노드와 link로 구성된 리스트이다. 아래 그림처럼 맨 앞과 끝에 Header와 Tailer 라는 노드로 구성되며 각 노드가 한 줄로 link되어있는 자료구조이다. 배열리스트가 주소공간에서 다닥다닥 밀집되어 있다면, 노드리스트는 link 덕분에 주소공간에서 서로 멀리 떨어져 있을 수 있다. 이런 성질 때문에 배열리스트에 비해 삽입, 삭제가 용이하다는 장점이 있다.
자바에서 노드리스트를 구현하고 싶다면 import java.util.LinkedList; 클래스를 사용하면 된다. 해당 클래스에는 아래와 같은 메소드들이 정의되어 있다. 이 외에도 collection을 이용하는 메소드가 더 있지만 가장 기본적인 것만 정리했다.
| 메소드 | 설명 |
| int size() | 리스트의 크기 러틴 |
| boolean isEmpty() | 리스트가 비었는지 아닌지 여부 리턴 |
| Object get(int i) | i번째 노드의 element 리턴 |
| Object getFirst() | 첫번째 노드의 element 리턴 |
| Object getLast() | 마지막 노드의 element 리턴 |
| Object set(int i, object e) | i번째 노드의 element를 e로 교체 후 교체 전 값 리턴 |
| void add(int i, Object e) | i번째에 노드 생성 후 element e 저장(첫번째 인자 생략 가능) |
| void addFirst(Object e) | 리스트 가장 앞에 노드 생성 후 element e 저장 |
| void addLast(Object e) | 리스트 가장 끝에 노드 생성 후 element e 저장 |
| Object remove(int i) | i번째 노드 삭제 후 값 리턴 |
| Object removeFirst() | 첫번째 노드 삭제 후 값 리턴 |
| Object removeLast() | 마지막 노드 삭제 후 값 리턴 |
| void clear() | 리스트의 모든 값 삭제 |
아래는 위 메소드들을 test한 예제이다.
LinkedList list = new LinkedList();
list.add('a');
list.add('c');
list.addFirst('x');
list.addLast('y');
list.set(1,'z');
Object k = list.get(2);
list.remove(k);
System.out.println(list);
int i = list.size();
list.clear();
if(list.isEmpty() == true){
System.out.println("리스트가 비었다");
System.out.println(i);
}
else{
System.out.println("리스트에 값이 있다");
}이중연결리스트(doubly linked list)는 양방향의 성질을 갖는 리스트이다. 각각의 노드는 이전, 이후 노드에 연결되는 두 개의 link와 element의 값을 갖는 노드와 연결되는 한 개의 link를 갖는다.
선행노드를 찾기 힘든 단순연결리스트의 단점을 보완해주는 장점이 있지만 구현이 어렵고 저장공간을 많이 차지한다는 단점이 있다. 아쉽게도 자바에는 이중연결리스트를 지원해주는 라이브러리는 없다. 구현해야하는 메소드들은 아래와 같다. 단순연결리스트에 있는 메소드와 다를바가 거의 없지만 직접 구현해야하는 이유는 삽입 삭제 시 link문제 때문이다.
| 메소드 | 설명 |
| Object set(int i, Object e) | i번째 노드의 값을 element e로 교체 후 이전 값 리턴 |
| Object get(int i) | i번째 노드의 값 리턴 |
| void addFirst(Object e) | 리스트 가장 앞에 노드 생성 후 element e 저장 |
| void add(int i, Object e) | i번째에 노드 생성 후 element e 저장 |
| void addLast(Object e) | 리스트 가장 끝에 노드 생성 후 element e 저장 |
| Object removeFirst() | 첫번째 노드 삭제 후 값 리턴 |
| Object remove(int i) | i번째 노드 삭제 후 값 리턴 |
| Object removeLast() | 마지막 노드 삭제 후 값 리턴 |
아래 그림은 add 메소드의 단계를 보여주는 그림이다.
아래 그림은 remove 메소드의 단계를 보여주는 그림이다.
아래는 위 메소드들을 구현한 예시 코드이다.
public class ListNode {
ListNode prev; //이전, 이후 노드를 기억할 수 있는 필드
ListNode next;
Object data; //노드의 데이터
public ListNode(){
prev = null;
next = null;
data = null;
}
public ListNode(Object data){
this.data = data;
prev = null;
next = null;
}
public ListNode(ListNode prev, ListNode next, Object data){
this.prev = prev;
this.next = next;
this.data = data;
}
}public class DoublyLinkedList {
public ListNode head; //리스트의 첫번째 노드
public ListNode tail; //리스트의 마지막 노드
public int size;
public DoublyLinkedList(){
head = null;
tail = null;
size = 0;
}
public void add(int i, Object e){
ListNode node = new ListNode(e); //(1)
if(i == 0){
addFirst(e);
}
else{
ListNode cur_prev = getNode(i-1);
ListNode cur_next = cur_prev.next;
node.prev = cur_prev; //(2)
node.next = cur_next; //(3)
cur_prev.next = node; //(4)
cur_next.prev = node; //(5)
size++;
}
}
public void addFirst(Object e){
ListNode node = new ListNode(e);
if(head == null){
head = node;
tail = node;
}
else{
node.next = head;
head = node;
}
size++;
}
public void addLast(Object e){
ListNode node = new ListNode(e);
if(head == null){
addFirst(e);
}
else{
tail.next = node;
node.prev = tail;
tail = node;
}
size++;
}
public Object remove(int i){
if(head == null){
System.out.println("이미 비어있는 리스트");
return null;
}
else{
if(i==0){
return removeFirst();
}
else if(i == size-1){
return removeLast();
}
else{
ListNode removeNode = getNode(i);
ListNode prev_remove = removeNode.prev; //(1)
ListNode next_remove = removeNode.next; //(2)
prev_remove.next = next_remove; //(3)
next_remove.prev = prev_remove; //(4)
size--;
return removeNode.data;
}
}
}
public Object removeFirst(){
if(head == null){
System.out.println("이미 비어있는 리스트");
return null;
}
else{
ListNode removeNode = head;
head = null;
head = removeNode.next;
head.prev = null;
size--;
return removeNode.data;
}
}
public Object removeLast(){
if(head == null){
System.out.println("이미 비어있는 리스트");
return null;
}
else{
ListNode removeNode = tail;
tail = null;
tail = removeNode.prev;
tail.next = null;
size--;
return removeNode.data;
}
}
public void setNode(int i, Object e){
ListNode current = getNode(i);
current.data = e;
}
public ListNode getNode(int i){
ListNode start = head;
for(int j = 0; j<i; j++){
start = start.next;
}
return start;
}
public void show_list(){
for(int i = 0; i<size; i++){
System.out.println(getNode(i).data);
}
}
}
(이 글이 도움이 됐다면 광고 한번씩만 클릭 해주시면 감사드립니다, 더 좋은 정보글 작성하도록 노력하겠습니다 :) )
https://github.com/srtktx/DataStructure_java
'간단 지식 > Data Structure' 카테고리의 다른 글
| 04. tree (0) | 2020.12.06 |
|---|---|
| 03. stack, queue (0) | 2020.11.21 |
| 01. 재귀호출(Recursion)과 반복호출 (0) | 2020.06.18 |