✨자료구조
자료구조(Data Structure)
- 일련의 동일한 타입의 데이터를 정돈하여 저장한 구성체
데이터 정돈 목적
- 프로그램에서 저장하는 데이터에 대해 탐색, 삽입, 삭제 등의 연산을 효율적으로 하기 위해
✨리스트
- 일련의 동일한 타입의 항목들
✏️배열
Array
- 동일한 타입의 원소들이 연속적인 메모리 공간에 할당되어 각 항목이 하나의 원소에 저장되는 기본적인 자료구조
- 미리 정해진 크기의 메모리 공간을 할당 받은 뒤 사용하므로 빈자리가 없어 삽입 시 오버플로우가 발생할 수 있음 이 때 프로그램의 안정성 향상을 위해 아래와 같은 방법을 사용할 수 있음
배열에 오버플로우가 발생하면 배열 크기를 2배로 확장
배열의 3/4이 비어 있다면 배열의 크기를 1/2로 축소 - 새 항목이 배열의 중간에 삽입되거나 중간에 있는 항목 삭제 시
그 뒤의 항목들을 한 칸씩 이동시켜야 함 -> 삭입/삭제 연산은 항상 O(1) 시간으로 수행 할 수 없음 - 원하는 원소의 위치를 찾는 것도 O(1)의 시간에 수행할 수 없음
✏️단순연결리스트
Singly Linked List
- 동적 메모리 할당을 이용해 리스트를 구현하는 가장 간단한 형태의 자료구조
- 동적 메모리를 할당 받아 노드를 저장
- 노드는 레퍼런스를 이용해 다음 노드를 가르키도록 만들어 노드들을 한 줄로 연결시킴
- 삽입이나 삭제 시 항목들의 이동이 필요 없음
- 배열에는 빈 공간이 있으나, 연결리스트는 빈 공간이 없음
- 항목을 탐색하려먼 항상 첫 노드부터 원하는 노드를 찾을 때까지 순차탐
색을 해야함
구현
노드 정의
node 객체는 항목을 저장할 item과 Node 레퍼런스를 저장하는 next를 가진다.
public class Node <E> {
private E item;
private Node<E> next;
public Node(E newItem, Node<E> node){ // 생성자
item = newItem;
next = node;
}
// get set 메소드
public E getItem() {return item;}
public Node<E> getNext(){return next;}
public void setItem(E newItem) { item = newItem; }
public void setNext(Node<E> nextNode) { next = nextNode; }
}리스트를 단순연결리스트로 구현한 SList
public class SList <E> {
protected Node head; // 연결 리스트의 첫 노드를 가리킴
private int size;
public SList() { // 생성자
head = null;
size = 0;
}
}탐색
원하는 노드가 나올 때까지 첫 노드부터 원하는 노드까지 순차적으로 탐색해야한다.
첫 노드의 item이 target 값과 같지 않다면 그 다음 노드를 p로 하여 p의 item이 target과 비교한다. 노드의 item이 target과 같을 때까지 반복한다. 모든 노드를 탐색하였는데 target 값이 없다면 -1을 리턴한다.
// 탐색
public int search(E target) {
Node p = head; // 첫 노드
for (int k = 0; k < size; k++){
if(target == p.getItem()){
return k; // 몇 번째 노드에 target 값이 있는 지를 반환
}
p = p.getNext(); // target 값과 같지 않다면 그 다음 노드를 p로
}
return -1; // 탐색 실패의 경우
}삽입
1) 맨 앞에 새로운 노드에 삽입하는 경우
public void insertFront(E newItem) {
head= new Node(newItem, head);
size++;
}2) p가 가리키는 노드의 다음에 삽입하는 경우
삽입하려는 노드의 next가 p의 next 노드를 가리키고, p의 next 를 새로 삽입하려는 노드를 가리키도록 수정한다.
newNode의 next -> 기존 p의 next
p의 next -> newNode
public void insertAfter(E newItem, Node p) {
p.setNext(new Node(newItem, p.getNext()));
size++;
}삭제
1) 맨 앞의 노드 삭제하는 경우
맨 처음 노드를 가리키는 head를 맨 앞의 노드의 다음 노드로 설정한다.
public void deleteFront(){
if(isEmtpy()) throw new NoSuchElementException();
head = head.getNext();
size--;
}2) p가 가리키는 노드의 다음 노드를 삭제하는 경우
p의 다음 노드의 next를 p의 next로 설정하고 삭제하려는 노드의 next를 null로 설정한다.
public void deleteAfter(Node p){
if(p == null ) throw new NoSuchElementException();
Node t = p.getNext();
p.setNext(t.getNext());
t.setNext(null);
size--;
}수행시간
- 탐색 연산 : 첫 노드부터 순차적으로 방문 -> O(N) 시간 소요
- 삽입/삭제 연산 : 각 상수 개의 레어런스를 갱신 -> O(1) 시간 소요
insetAfter()나 deleteAfter()의 경우 특정 노드 p의 레퍼런스가 주어지지 않으면 head부터 p를 찾기 위해 탐색해야하므로 O(N) 시간 소요
✏️이중연결리스트
Doubly Linked List
- 각 노드가 두 개의 레퍼런스로 각각 이전 노드와 다음 노드를 가리키는 연결리스트
구현
노드 정의
public class DNode <E>{
private E item;
private DNode previous; // 이전 노드
private DNode next; // 다음 노드
public DNode(E newItem, DNode p, DNode q){
item = newItem;
previous = p;
next = q;
}
//get, set 메소드
}이중연결리스트로 구현한 DList
- 생성자에서 head에 연결리스트의 첫 노드를 가리키는 레퍼런스 저장
- tail - 연결리스트의 마지막 노드를 가리키는 레퍼런스를 저장
- head와 tail 두 노드들은 실제 항목을 저장하지 않는 더미 노드
public class DList <E>{
protected DNode head, tail;
protected int size;
public DList() { // 생성자
head = new DNode(null, null, null);
tail = new DNode(null,head,null); //tail의 이전 노드를 head로 만든다
head.setNext(tail); //head의 다음 노드를 tail로 만든다
size = 0;
}
}삽입
1) 특정 노드 앞에 삽입
public void insertBefore(DNode p, E newItem){
DNode t = p.getPrevious();
DNode newNode =new DNode(newItem, t, p);
t.setNext(newNode);
p.setPrevious(newNode);
size++;
} 2) 특정 노드 뒤에 삽입
// 특정 노드 뒤에 삽입
public void insertAfter(DNode p, E newItem){
DNode t = p.getNext();
DNode newNode =new DNode(newItem,p ,t );
t.setPrevious(newNode);
p.setNext(newNode);
size++;
}삭제
public void delete(DNode x){
DNode f = x.getNext();
DNode r = x.getPrevious()
r.setNext(f);
f.setPrevious(r);
size --;
}수행시간
- 탐색 연산 : head 또는 tail로부터 노드들을 순차적으로 탐색 -> O(N) 시간 소요
- 삽입/삭제 연산 : 각각 상수 개의 레퍼런스만 갱신 -> O(1) 시간 수행
✏️원형연결리스트
Circular Linked List
- 마지막 노드가 첫 노드와 연결된 단순연결리스트
- 마지막 노드의 레퍼런스가 저장된 last가 단순연결리스트의 head와 같은 역할
- 리스트가 empty가 아니면 어떤 노드도 null 레퍼런스를 가지고 있지 않으므로 null 조건 검사를 하지 않아도 됨
- 반대 방향으로 노드들을 방문하기 쉽지 않음
- 무한 루프 발생 주의
- 여러 사람들이 차례로 돌아가며 하는 게임 구현에 적합한 자료구조
- 많은 사용자들이 동시에 사용하는 컴퓨터에서 cpu 할당하는 운영체제에도 사용됨
구현
노드 정의
- 원형연결리스트의 노드 클래스는 단순연결리스트의 노드 클래스와 같다.
환형연결리스트로 구현한 CList
public class CList <E>{ // 생성자
private Node last; // 리스트의 마지막 노드를 가리킴
private int size;
public CList() {
last = null;
size=0;
}
}삽입
last가 가리키는 노드의 다음에 새로운 노드를 삽입한다.
newNode - 새 항목을 저장할 새로운 노드 생성
리스트의 요소가 없다면 last는 null이고 last를 새 노드로 지정한다.
요소가 있다면 [ last -> 기존 last.next 노드 ]를 [ last -> 새로운 노드 -> 기존 last.next 노드 ]로 변경한다.
public void insert(E newItem){ // last가 가리키는 노드의 다음에 새노드 삽입
Node newNode = new Node(newItem, null); // 새 항목을 저장할 새로운 노드 생성
if(last == null){
newNode.setNext(newNode);
last = newNode;
}
else{
newNode.setNext(last.getNext()); //newNode의 다음 노드가 last가 가리키는 노드의 다음 노드가 되도록
last.setNext(newNode);
}
size++;
}삭제
public Node delete(){ //last가 가리키는 노드의 다음을 제거
Node x = last.getNext(); //x는 리스트의 첫 노드
if(x==last){ // 리스트에 노드가 한 개만 있는 경우
last=null;
}
else{
last.setNext(x.getNext()); // last가 가리키는 노드의 다음노드가 x의 다음 노드임
x.setNext(null);
}
size--;
return x;
}수행시간
- 탐색 연산 : last로부터 노드들을 순차적으로 탐색 -> O(N)
- 삽입/삭제 연삭 : 각 상수 개의 레퍼런스를 갱신 -> O(1)
수행시간 비교
최악의 경우 수행시간 비교
참고
양성봉 저,『자바와 함께하는 자료구조의 이해』, 생능출판사(2017)
자료구조 게시글은 모두 위 책을 참고하였습니다
