[Java] List

리스트

리스트 정의

• 리스트는 일련의 동일한 타입의 항목들
• 실생활 예 : 학생 명단, 시험 성적, 서점의 신간 서적
• 리스트의 구현
  • 1차원 배열
  • 단순 연결 리스트
  • 이중 연결 리스트
  • 환형 연결 리스트

배열

배열 정의

• 배열은 동일한 타입의 원소들이 연속적인 메모리 공간에 할당되어 각 항목이 하나의 원소에 저장되는 기본적인 자료 구조
• 특정 원소에 접근할 때에는 배열의 인덱스를 이용하여 O(1) 시간에 접근할 수 있다.
• 새 항목이 배열 중간에 삽입되거나 중간에 있는 항목을 삭제하면, 뒤 따르는 항목들을 한 칸 씩 뒤로 또는 앞으로 이동시켜야 하므로 삽입이나 삭제 연산은 항상 O(1) 시간에 수행할 수 없다. (최악은 O(n))

자바 언어 특성 반영한 표현

a → a[0] a[1] a[2] a[3] a[4] a[5] a[6] a[7]

• a가 배열 이름인 동시에 배열의 첫 번째 원소의 레퍼런스를 저장
• a[i]는 인덱스 i를 가지는 원소를 가리키는 레퍼런스(주소)
• 각 원소 a[i]는 a가 가지고 있는 레퍼런스에 원소의 크기(바이트) x i 를 더하여 a[i]의 레퍼런스를 계산
• a[i] = a + (원소의 크기 x i)
• char 배열의 원소의 크기 = 2바이트, int 배열의 원소의 크기 = 4바이트

Overflow

• 배열은 컴파일 할 때 미리 정해진 크기의 메모리 공간을 할당 받은 뒤 사용해야 하므로, 빈자리가 없어 새 항목을 삽입할 수 없는 상황(Overflow) 발생
• Overflow가 발생하면 에러 처리를 하여 프로그램을 정지시키는 방법이 주로 사용되지만 프로그램 안정성 향상을 위해 다음과 같은 방법 사용
  • 배열에 overflow가 발생하면 배열 크기를 2배로 확장하고 3/4이 비어 있다면 배열 크기를 1/2로 축소 → 동적 배열(프로그램 실행 동안 할당된 배열)

ArrList 클래스

리스트를 배열로 구현 : ArrList 클래스

import java.utril.NoSuchElemenException;  // Line01
public class ArrList <E> {
    private E a[];  // 리스트 항목들을 저장한 배열
    private int size;  // 리스트 항목 수
    public ArrList() {  // 생성자
        a = (E[]) new Object[1];  // 최초로 1개 원소가진 배열 생성
        size = 0;  // 홍목 수를 0으로 초기화
    }
    // 탐색, 삽입, 삭제 연산을 위한 메소드 선언
    public E peek(int k) {
        if (size == 0) {
            throw new NoSuchElementException;
        return a[k];
    }
    public void insertLast (E newItem) {
        if (size == a.length) {
            resize(2*a.length);
        }
        a[size++] = newItem;
    }
    public void insert (E newItem, int k) {
        if (size == a.length) {
            resize(2*a.length);
        }
        for (int i = xize -1; i >= k; i--) {
            a[i+1] a[i];
        }
        a[k] = newItem;
        size++;
    }
    // 배열의 k번째 항목 삭제 및 사이즈 줄이기
    public E delete(int k) {
    if (isEmpty()) throw new NoSuchElementException();
    E item = a[k];
    for (int i = k; i < size; i++) {
        a[i] = a[i+1];
    }
    size--;
    if (size > 0 && size == a.length/4) {
        resize(a.length/2);
    return item;
    }
    // 사이즈 조절
    private void resize(int newSize) {
    Object[] t = new Object[newSize]'
    for (int i = 0; i < size; i++) {
        t[i] = a[i];
    a = (E[]) t;  // 기존 배열인 a는 가비지 컬렉션에 의해 처리
    }
} 

• Line01: 리스트가 empty인 상황에서 항목 읽으려고 하면 (underflow 발생) 프로그램 정지시키는 예외처리
• peak() 메소드는 인덱스 이용하여 배열 원소 직접 접근 하여 O(1)
• 삽입 삭제는 새 항목 중간 삽입, 중간에 있는 항목을 삭제한 후 뒤따르는 항목을 한 칸씩 앞이나 뒤로 이동해야 하므로 각각 최악의 경우는 O(N) 시간 소요
• 새 항목을 가장 뒤에 삽입하는 경우 O(1)
• 배열으 크기를 확대 또는 축소하는 것도 최악의 경우 O(N) 시간
• 상각분석에 따르면 삽입이나 삭제의 평균 수행시간은(O(1)
• ※ 상각분석은 자료구조나 알고리즘의 효율성을 평가하는 분석 방법입니다. 이 방법은 최악의 경우가 드물게 발생한다는 점을 고려하여, 일련의 연산에 대한 평균적인 성능을 분석합니다. 상각분석을 통해 개별 연산의 비용이 높더라도 전체적인 평균 성능이 좋을 수 있음을 보여줄 수 있습니다.

연결리스트

단순연결리스트

단순연결리스트 정의

• 단순연결리스트(Singly Linked List)는 동적 메모리 할당을 이용해 리스트를 구현하는 가장 간단한 형태의 자료 구조
• 동적 메모리 할당을 받아 노드를 저장하고, 노드는 레퍼런스를 이용하여 다음 노드를 가리키도록 만들어 노드들을 한 줄로 연결시킴
• 연결리스트에서는 삽입이나 삭제 시 항목들의 이동이 필요 없음
• 배열의 경우 최초의 배열 크기를 예측하여 결정해야 하므로 대부분의 경우에 배열에 빈 공간을 가지고 있으나, 연결리스트는 빈공간이 존재하지 않음
• 연결리스트에서는 항목을 탐색하려면 항상 첫 노드부터 원하는 찾을 때까지 차례로 방문하는 순차탐색 (SequentialSearch)을 해야 함

단순연결리스트의 노드를 위한 Node 클래스

// 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;
    }
    public E getItem() { return item; }
    public Node<E> getNext( return next; }
    public void setItem(E NewItem) { item = newItem; }
    public void setNext(Node<E> newNext) { next = newNext; }
}

리스트를 단순연결리스트로 구현한 SList 클래스

import java.util.NoSuchElementException;
public class SList <E> {
    protected Node head;  // 연결 리스트 첫 노드 가리킴
    private int size;
    public SList() {  // 연결리스트 생성자
        head = null;
        size = 0;
    // 탐색, 삽입, 삭제 연산 위한 메소드 선언
    public int search(E target) {
        Node p = head;
        for (int k = 0; k < size; k++) {
            if (tarket == p.getItem()) return k;
            p = p.getNext();
        }
        return -1;  // 탐색 실패
    }
    public void insertFront(E newItem) {
        head = new Node(newItem, head);
        size++;
    }
    public void insertAfter(E newItem, Node p) {
        p.setNext(new Node(newItem, p.getNext()));
        size++;
    }
    public void deletFront() {
        if (size == 0) throw new NoSuchElementException();
        head = head.getNext();
        size--;
    }
    public void deleteAfter(Node p) {
        if (p == null) throw new NoSuchElementException();
        Node t = p.getNext();
        p.setNext(t.getNext());
        t.setNext(null);
    }
}

수행시간

• search() 연산: 탐색을 위해 연결리스트의 노드들을 첫 노드부터 순차적으로 방문해야 하므로 O(N) 시간이 소요
• 삽입이나 삭제 연산: 각각 상수 개의 레퍼런스를 갱신하므로 O(1) 시간이 소요
  • 단, insertAfter()나 deleteAfter()의 경우에 특정 노드 p의 레퍼런스가 주어지지 않으면 head로 부터 p를 찾기 위해 search()를 수행해야 하므로 O(N) 시간이 소요

이중연결리스트

이중연결리스트 정의

• 이중연결리스트(Double Linked List)는 각 노드가 두 개의 레퍼런스를 가지고 각각 이전 노드과 다음 노드를 가리키는 연결 리스트
• 단순연결리스트 삽입이나 삭제할 때 반드시 이전 노드를 기리키는 레퍼런스를 추가로 알아내야 하고, 역방향으로 노드들을 탐색할 수 없음
• 이중연결리스트는 단순연결리스트의 이러한 단점을 보완하나, 각 노드마다 추가로 한 개의 레퍼런스를 추가로 저장해야 한다는 단점을 가짐

이중연결리스트의 노드를 위한 DNode 클래스

public class DNode <E> {
    private E item;
    private DNode previous;
    private Dnode next;
    public DNode (E newItem, DNode p, DNode q) {
        item = newItem;
        previeous = p;
        next = q;
    }
    public E getItem() {return item;}
    public DNode getPrevious() {return previous;}
    public DNode getNext() {return next;}
    public void setItem(E NewItem) {item = newItem;}
    public void setPrevious(DNode p) {previous = p;}
    public void setNext(DNode q) {next = q;}
}

이중연결리스트를 위한 DList 클래스

import java.util.NoSuchElementException;
public class DList <E> {
    protected DNode head, tail;
    protecte int size;
    public DList() {
        // head와 tail 두 노드들은 항목 저장하지 않는 Dummy 노드
        head = new DNode (null, null, null);
        tail = new DNode (null, head, null);
        head.lsetNext(tail);
        size = 0;
    }
    // 삽입, 삭제 연산을 위한 메소드 선언
    public void insertBefore(DNode p, E newItem) {
        DNode t = p.getPrevious();
        DNode newNode = new DNode(newItem, t, p);
        p.setPrevious(newNode);
        t.setNext(newNode);
        size++;
    }
    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) {
        if (x == null) throw new NoSuchElementException();
        DNode f = x.getPrevious();
        DNode r = x.getNext();
        f.setNext(r);
        r.setPrevious(f);
        size--;
    }
}

수행시간

• 이중연결리스트에서 삽입이나 삭제 연산은 각가 상수 개의 레퍼런스만을 갱신하므로 O(1) 시간에 수행
• 탐색 연산 : head 또는 tail로부터 노드들을 순차적으로 탐색해야 하므로 O(N) 시간 소요

원형연결리스트

원형연결리스트 정의

• 원형연결리스트(Circular Liked List)는 마지막 노드가 첫 노드와 연결된 단순 연결리스트
• 원형연결리스트에서 마지막 노드의 레퍼런스가 저장되 last가 단순연결리스트의 head와 같은 역할
• 마지마거 노드와 첫 노드를 O(1) 시간에 방문할 수 있는 장점
• 리스트가 empty가 아니면 어떤 노도도 null 레퍼런스를 가지고 있지 않으므로 프로그램에서 null 조건을 검사하지 않아도 되는 장점
• 원형연결리스트에서는 반대 방향으로 노드들을 방문하기 쉽지 않으며, 무한 루프에 발생할 수 있음에 유의할 필요

원형연결리스트의 응용

• 여러 사람이 차례로 돌아가며 하는 게임을 구현하는데 적합한 자료구조
• 많은 사람들이 동시에 사용하는 컴퓨터에서 CPU 시간을 분할하여 작업들에 할당하는 운영체제에 사용
• 이항힙(Binomial Heap)이나 피보나치힙(Fibonacci Heap)과 같은 우선순위큐를 구현하는 데에도 원형연결리스트가 부분적으로 사용

원형연결리스트를 위한 CList 클래스

import java.util.NoSuchElementException;
public class CList <E> {
    private Node last;
    Private int size;
    public CList() {
        last = null;
        size = 0;
    }
    // 삽입, 삭제 연산을 위한 메소드 선언    
    public void insert(E, newItem) {
        Node newNode = new Node(newItem, null);
        if (last == null) {
            newNode.setNext(newNode);
            last = newNode;
        } else {
            newNode.setNext(last.getNext());
            last.setNext(newNode);
        }
        size++;
    }
    public Node delete() {
        if (isEmpty()) throw new NoSuchElementException();
        Node x = last.getNext();
        if (x == last) last = null;  // node가 한 개인 경우
        else {
            last.setNext(x.getNext());
            x.setNext(null);
        }
        size--;
        return x;
    }
}

수행시간

• 원형연결리스트에서 삽입이나 삭제 연산 각각 상수 개의 레퍼런스를 갱신하므로 O(1) 시간에 수행
• 탐색 연산 : last로부터 노드들을 순차적으로 탐색해야 하므로 O(N) 소요

출처: 경기대학교|소프트웨어중심대학사업단