자료구조. 리스트(List)

Theme. 리스트(list)

 

여러 개의 데이터를 저장하고, 임의의 위치에 새로운 데이터를 추가하거나, 데이터의 삭제가 가능하고, 임의의 위치의 데이터를 읽을 수 있고, 용량에 제한이 없고.... 모두 리스트의 여러 특징들 중에 하나이다.

 

이러한 리스트를 구현하는 대표적인 두 가지 방법은 배열(ArrayList), 연결리스트(LinkedList)가 있다.

리스트는 기본적으로 삽입(insert), 삭제(remove), 검색(search) 등 기본적인 연산을 제공하는데, 이러한 연산 과정에서 배열과 연결리스트의 장단점이 드러난다.

 

먼저, 배열의 가장 큰 특징 중 하나는 크기가 고정되어 있다는 것이다. 이로 인해, 데이터를 추가하려는데 배열의 크기를 넘어서게 된다면, 배열을 재할당(reallocation)해줘야 한다. 재할당하는 3가지 방법에 대해서는 아래 코드에 나타내도록 한다. 또한, 리스트의 중간에 원소를 삽입하거나 삭제할 경우 다수의 데이터를 옮겨야 한다. 가령, 원소를 삽입하려면 삽입하려는 위치(인덱스)부터 그 이후의 원소들을 모두 뒤로 한칸씩 밀어줘야하고, 삭제의 경우에는 앞으로 땡겨줘야 한다.

 

연결리스트는 배열과는 다르게 다른 데이터의 이동없이 중간에 데이터를 삽입하거나 삭제할 수 있다는 장점이 있고, 크기가 고정되어 있는 것이 아니므로 길이의 제한이 없다.

하지만, 랜덤 엑세스가 불가능하다는 단점이 있다. 

랜덤 엑세스에 대해 간단하게 설명하면,

먼저 연결리스트는 아래와 같이 노드들의 연결된 형태이다.(head는 첫번째 노드의 주소를 저장하고 있다.)

이때, 각각의 노드들이 다음 노드들의 주소를 링크 필드에 저장하고 있기 때문에 어떤 노드에 접근하고 싶다면, 첫번째 노드부터 순차적으로 주소를 따라가면서 접근해야 한다. 이는 배열에서 특정 원소에 접근하고 싶다면 해당 인덱스로 바로 접근할 수 있는 것과 차이가 있다. 즉, 배열은 랜덤 엑세스가 가능하지만, 연결리스트는 랜덤 엑세스가 불가능하다.

 

 

Theme. ArrayList의 구현

MyArrayList 클래스를 생성하여 ArrayList의 일부 메서드들을 구현하도록 한다.

 

import java.util.Arrays;
 
// 하나의 array 리스트를 표현하는 클래스
public class MyArrayList<E> {
 
    private static final int INIT_CAPACITY = 10;
    private E[] theData;
    private int size; // 현재 배열의 크기
    private int capacity;
 
    public MyArrayList() {
        theData = (E[]) new Object[INIT_CAPACITY];
        size = 0;
        capacity = INIT_CAPACITY;
    }
 
    // 해당 인덱스에 데이터를 추가
    public void add(int index, E anEntry) {
 
        if (index < 0 || index > size) {
            throw new ArrayIndexOutOfBoundsException(index);
        }
        if (size >= capacity) {
            reallocate();
        }
        for (int i = size - 1; i >= index; i--) { // 해당 인덱스를 포함하여 그 이후의 모든 데이터들을 한칸씩 뒤로 보내줌
            theData[i + 1] = theData[i];
        }
        theData[index] = anEntry;
        size++;
 
    }
 
    // 배열재할당! 배열의 값은 그대로 두고, 배열의 크기를 증가시킴
    private void reallocate() {
        // 방법 1
        E[] tmp = (E[]) new Object[capacity * 2];
        for (int i = 0; i < size; i++) {
            tmp[i] = theData[i];
        }
        theData = tmp;
        capacity *= 2;
 
        // 방법 2
        capacity *= 2;
        E[] tmp = (E[]) new Object[capacity];
        System.arraycopy(theData, 0, tmp, 0, size);
        theData = tmp;
 
        // 방법 3
        capacity *= 2;
        theData = Arrays.copyOf(theData, capacity);
    }
 
    // 데이터를 추가(맨 뒤에)
    public void add(E anEntry) {
        add(size, anEntry);
    }
 
    // 배열 내 동일한 데이터가 존재하는지를 판단하고, 있다면 그 위치(인덱스)를 반환
    public int indexOf(E anEntry) {
        for (int i = 0; i < size; i++) {
            if (theData[i].equals(anEntry)) {
                return i;
            }
        }
        return -1;
    }
 
    // get, set
    public E get(int index) {
        if (index < 0 || index >= size) {
            throw new ArrayIndexOutOfBoundsException(index);
        } else {
            return theData[index];
        }
    }
 
    public E set(int index, E newValue) {
        if (index < 0 || index >= size) {
            throw new ArrayIndexOutOfBoundsException(index);
        }
        E oldValue = theData[index];
        theData[index] = newValue;
        return oldValue;
    }
 
    // remove
    public E remove(int index) {
        if (index < 0 || index >= size) {
            throw new ArrayIndexOutOfBoundsException(index);
        } 
        E returnValue = theData[index];
        for (int i = index + 1; i < size; i++) {
            theData[i - 1] = theData[i];
        }
        size--;
        return returnValue;
    }
 
}
 

 

 

Theme. SingleLinkedList의 구현

1. 연결 리스트에서 하나의 노드를 표현하기 위한 클래스

 

// 연결리스트에서 하나의 노드를 표현하기 위한 클래스
public class Node<T> {
 
    public T data; // 노드의 데이터 필드
    public Node<T> next; // 노드의 링크필드
 
    public Node(T item) {
        data = item;
        next = null;
    }
 
}
 

 

2. 하나의 연결리스트를 표현하는 클래스

 

// 하나의 연결리스트를 표현하는 클래스
public class MySingleLinkedList<T> {
    public Node<T> head; // 첫번째 노드의 주소 참조
    public int size; // 노드의 개수
 
    public MySingleLinkedList() {
        head = null;
        size = 0;
    }
 
    // 연결리스트 첫번째 노드 앞에 새로운 노드를 추가하는 메서드
    public void addFirst(T item) {
        Node<T> temp = new Node<T>(item); // 새로운 노드를 생성하고 추가할 데이터 저장
        temp.next = head; // 새로운 노드의 next(링크필드)가 기존 첫번째 노드 주소를 저장
        head = temp; // head가 새로운 첫번째 노드 주소를 저장
        size++; // 노드가 추가됐으니 노드의 개수 += 1
        
        /* 주의할 점 정리 */
        /*
        Node<T> newNode = new Node<T>(item); // T를 type parameter로 가지는 다른 클래스의 객체 생성 가능
        Node<T>[] arr1 = new Node<T>[100]; // T를 type parameter로 가지는 다른 클래스의 배열 생성 불가능
        
        T t = new T(); // T 타입의 객체 생성 불가능
        T[] arr2 = new T[100]; // T 타입의 배열 생성 불가능
        */
        
    }
 
    // 이전 노드 객체가 매개변수로 주어졌을 때, 그 다음에 새로운 노드를 추가하는 메서드
    public void addAfter(Node<T> before, T item) {
        Node<T> temp = new Node<T>(item); // 새로운 노드를 생성하고 추가할 데이터 저장
        temp.next = before.next; // 새로운 노드의 next(링크필드)가 before 노드가 저장하던 다음 노드의 주소를 저장
        before.next = temp; // before 노드의 next가 새로운 노드의 주소를 저장
        size++; // 노드가 추가됐으니 노드의 개수 += 1
    }
 
    // 연결리스트의 첫번째 노드(head 노드)를 삭제하고 그 노드에 저장된 데이터를 반환하는 메서드
    public T removeFirst() {
        if (head == null) {
            return null;
        } else {
            T temp = head.data; // 삭제될 첫번째 노드의 데이터를 temp에 저장
            head = head.next; // head가 현재의 head 노드의 다음 노드를 가리키게 됨
            size--; // 노드가 삭제됐으니 노드의 개수 -= 1
            return temp; // 저장된 데이터 반환
        }
    }
 
    // before가 가리키는 노드의 다음 노드를 삭제하고 그 노드에 저장된 데이터를 반환하는 메서드
    public T removeAfter(Node<T> before) {
        if (before.next == null) { // 삭제하려는 노드가 null인 경우
            return null; 
        } else {
            T temp = before.next.data;
            before.next = before.next.next; // 삭제될 노드의 다음 노드의 주소를 before가 가리키는 노드의 next가 저장
            size--; // 노드가 삭제됐으니 노드의 개수 -= 1
            return temp; // 저장된 데이터 반환
        }
    }
 
    // 매개변수 item과 동일한 data를 가지는 노드의 인덱스 넘버를 반환하는 메서드(찾지 못하면 -1 반환)
    public int indexOf(T item) {
        // 연결리스트의 노드들을 처음부터 순서대로 방문하는 순회(traverse) 이용!
        Node<T> p = head; // 순회를 하면서 각 노드들을 가리킬 변수 p 선언하고, head가 가리키는 주소 저장
        int index = 0;
        while (p != null) { // 끝까지 돌도록
            if (p.data.equals(item)) { // equals 메서드를 사용하는 것!
                return index;
            }
            p = p.next; // p가 다음 노드를 가리키도록! ( 한칸 전진 )
            index++; // index도 다음 노드로 넘어가니까 +1
        }
        return -1;
    }
 
    // 연결리스트의 index번째 노드의 주소를 반환
    public Node<T> getNode(int index) {
        if (index < 0 || index >= size) { // index가 연결리스트의 범위를 벗어난 경우
            return null;
        } else {
            Node<T> p = head; // 순회를 하면서 각 노드들을 가리킬 변수 p 선언하고, head가 가리키는 주소 저장
            for (int i = 0; i < index; i++) { // 주어진 index번째 노드를 가리키도록 p를 전진시킨다.
                p = p.next;
            }
            return p;
        }
    }
 
    // 연결리스트의 index번째 저장된 데이터를 반환
    public T get(int index) {
        if (index < 0 || index >= size) { // index가 연결리스트의 범위를 벗어난 경우
            return null;
        } else {
            Node<T> p = head; // 순회를 하면서 각 노드들을 가리킬 변수 p 선언하고, head가 가리키는 주소 저장
            for (int i = 0; i < index; i++) { // 주어진 index번째 노드를 가리키도록 p를 전진시킨다.
                p = p.next;
            }
            return p.data;
        }
    }
 
    // 연결리스트의 index번째 위치에 새로운 노드를 삽입
    public void add(int index, T item) {
 
        if (index < 0 || index > size) { // index가 연결리스트의 범위를 벗어난 경우
            return; 
        }
        if (index == 0) {
            addFirst(item);
//            Node<T> temp = new Node<T>(item);
//            temp.next = head;
//            head = temp;
//            size++;
        } else {
            Node<T> node = getNode(index - 1);
            addAfter(node, item);
//            Node<T> p = head;
//            for (int i = 0; i < index - 1; i++) {
//                p = p.next;    // p는 index-1번째 노드를 가리키고 있음
//            }
//            Node<T> temp = new Node<T>(item);
//            temp.next = p.next;    // index번째 노드의 주소를 temp의 next에 저장
//            p.next = temp;    // 새로 추가된 노드를 index-1번째 노드의 next가 가리키도록 함
//            size++;
        }
    }
 
    // 연결리스트의 index번째 노드를 삭제하고, 그 노드에 저장된 데이터를 반환
    public T remove(int index) {
        if (index < 0 || index >= size) { // index가 연결리스트의 범위를 벗어난 경우
            return null;
        }
 
        if (index == 0) {
            return removeFirst();
//            Node<T> temp = head;
//            head = head.next;
//            size--;
//            return temp.data;
        } else {
            Node<T> prev = getNode(index - 1);
            return removeAfter(prev);
//            Node<T> p = head;
//            for (int i = 0; i < index-1; i++) {
//                p = p.next;    // index-1 번째 노드 가리키고 있음
//            }
//            Node<T> temp = p.next; // index번째 노드 가리킴
//            p.next = temp.next;
//            size--;
//            return temp.data;
        }
 
    }
 
    // 매개변수로 주어진 값과 동일한 데이터값을 가지는 노드를 찾아 삭제하고, 삭제된 노드에 저장된 데이터 값을 반환
    public T remove(T item) {
        // q는 항상 p의 직전노드를 가리키게 하고 순회!
        Node<T> p = head;
        Node<T> q = null;
        while (p != null && !p.data.equals(item)) {
            q = p;
            p = p.next;
        }
        // while문을 빠져나왔을 때, p가 삭제할 노드를 가리키고 있다면, q는 바로 그 전 노드를 가리키고 있음
        if (p == null) {
            return null;
        }
        if (q == null) { // 첫번째 노드가 찾던 노드였던 경우(p는 첫번째 노드를 가리키고 있는 상태)
            return removeFirst();
        } else {
            return removeAfter(q);
        }
 
    }
 
    public static void main(String[] args) {
        
    }
 
}