[자료구조 및 알고리즘] Ch02. 리스트(List)

리스트(List)

🔊 패스트캠퍼스 "한 번에 끝내는 컴퓨터 공학 전공필수 & 인공지능 심화 초격차 패키지 Online." 강의를 보고 공부하면서 정리한 노트 게시물입니다.

Ch02-01. 리스트(List)

• 선형적인 자료구조
• 데이터를 일렬로 늘여 놓은 형태

• 순서

• List
  • ArrayList
  • LinkedList
    • Single Linked List
    • Double Linked List

ArrayList

• 배열 기반의 리스트
• 메모리 공간을 연속적으로 사용

Main.java

import java.util.ArrayList;
import java.util.List;

public class Main {
    public static void main(String[] args) {
        List<String> list = new ArrayList<>();

        // string 타입 요소 추가
        list.add("Hello");
        list.add("World");
        list.add("GRACE"); 

        System.out.println(list);

        list.remove("Hello"); // 요소 제거

        System.out.println(list);

        System.out.println(list.get(0)); // index로 출력
    }
}

ArrayList는 배열 기반이기 때문에, 배열과 동일한 방식으로 index를 사용하게 된다. index를 통한 데이터 접근은 random access 방식이기 때문에 리스트의 데이터가 100개가 있든 1000개가 있든 인덱스만 알고 있다면, 항상 동일한 시간을 소요해서 데이터에 접근을 할 수 있다.

또 ArrayList는 컴퓨터의 실제 물리적인 메모리 공간에서도 연속적인 공간을 사용하기 때문에, 컴퓨터가 연산을 하기 쉬운 구조를 갖고 있다. 그래서, 이전 인덱스에서 다음 인덱스로 접근하는 속도가 빠르다.

반면에, LinkedList는 데이터를 논리적으로 연결을 시켜서 마치 연속된 형태의 데이터처럼 쓸 수 있도록 구현은 되있지만, 실제 컴퓨터 메모리 상에서는 물리적인 공간을 연속적으로 차지하고 있는 형태가 아니기 때문에, 데이터 간의 이동 자체에는 시간이 더 소요된다.

삽입

위와 같이 삽입 하고자 하는 경우, 삽입 하고자 하는 인덱스의 위치로부터 데이터가 위치한 제일 뒤의 인덱스까지 모두 한 칸씩 뒤로 데이터를 미뤄주는 작업을 먼저 해야한다. 그림과 같이 사이의 데이터가 2개라면, 데이터를 옮겨주는 연산을 2번 해야하고, 1000개라면 1000번… N개라면 N번 데이터를 옮겨주는 연산을 해야하기 때문에, 시간 복잡도는 $O(N)$이 된다.

삭제

인덱스 기반의 데이터를 삭제할 때도 마찬가지로, 데이터를 이동 시켜주는 작업을 진행해야한다. (마찬가지로, 시간 복잡도 $O(N)$으로 똑같음)

탐색 by index

ArrayList에서 index를 통한 데이터 탐색은, Random Access로 해당 위치에 Direct로 접근을 하게 된다. 그렇기 때문에, 데이터가 아무리 많아져도 한 번에 해당 위치에 접근해서 데이터를 가져올 수 있기 때문에 index를 통한 데이터 탐색 속도는 매우 빠르다. (이렇게 데이터의 개수와 상관없이 연산의 속도가 일정하다면, 시간 복잡도는 $O(1)$임)

LinkedList는 이런 방식의 접근이 불가능하다.

02. ArrayList 구현

ArrayList

main > java > list > IList.java

package list;

public interface IList<T> {
// 제네릭으로 <T>가 들어간 이유 :: int가 들어갈 수도 있고, String이 들어갈 수도 있고
// 어떤 타입이 들어갈지 모르기 때문에, 관형적으로 T라는 이름을 써줌.
    void add(T t);

    void insert(int index, T t);

    void clear();

    boolean delete(T t);

    boolean deleteByIndex(int index);

    T get(int index);

    int indexOf(T t);

    boolean isEmpty();

    boolean contains(T t);

    int size();
}

main > java > list > MyArrayList.java

package list;

import java.util.Arrays;

public class MyArrayList<T> implements IList<T> {
    private static final int DEFAULT_SIZE = 50;

    private int size; // ArrayList에 데이터가 몇개 들어있는지 확인해주는 변수
    private T[] elements; // 어떤 타입이 들어올지 모르기 때문에 T타입의 array 선언

    // 생성자
    public MyArrayList() {
        this.size = 0;
        this.elements = (T[]) new Object[DEFAULT_SIZE];
    }

    // 추가 함수 : 가장 뒤에 데이터를 넣는 함수
    @Override
    public void add(T t) {
        if (this.size == this.elements.length) { // 배열이 꽉 차면,
            // 사이즈를 2배로 늘려준 다음에 기존 elements에 있는 데이터를 전부 다 옮김
            this.elements = Arrays.copyOf(this.elements, this.size * 2);
        }
        this.elements[this.size++] = t;
    }

    // 우리가 정해준 인덱스에다가 데이터를 삽입하는 함수
    @Override
    public void insert(int index, T t) {
        if (this.size == this.elements.length) {
            this.elements = Arrays.copyOf(this.elements, this.size * 2);
        } // array의 사이즈가 꽉 차 있을 경우면, array 크기 늘림

        for (int i = index; i < this.size; i++) {
            this.elements[i+1] = this.elements[i];
        } // 삽입 하려고 하는 인덱스부터 현재 데이터가 있는 시점까지 한 칸씩 뒤로 민다.
        this.elements[index] = t; // 삽입하고자 하는 데이터를 해당 인덱스에 삽입해주고,
        this.size++; // 사이즈 1 늘려줌
    }

    @Override
    public void clear() {
        this.size = 0;
        this.elements = (T[]) new Object[DEFAULT_SIZE];
    }

    // 내가 삭제하고 싶은 데이터를 찾아서 삭제하는 메소드
    @Override
    public boolean delete(T t) {
        for (int i = 0; i < this.size; i++) {
            if (this.elements[i].equals(t)) { // 이 조건에 부합한다면, 삭제하고자 하는 데이터라는 것임
                // 지우는 작업이므로 한 칸씩 앞으로 땡겨 옴
                for (int j = i; j < this.size-1; j++) { // 지우고자 하는 element의 인덱스가 i에 걸려있으므로 i부터
                    this.elements[j] = this.elements[j+1]; // 앞으로 땡겨옴
                }
                this.size--;
                return true;
            }
        }
        return false;
    }

    // 위치 기반으로 해서 해당 위치에 있는 데이터를 지우는 메소드
    @Override
    public boolean deleteByIndex(int index) {
        if (index < 0 || index > this.size - 1) {
            return false;
        } // 인덱스가 잘못 들어오는 경우 처리해주는 부분
        for (int i = index; i < this.size-1; i++) { // 아래에서 i+1까지 갈 것이기 때문에 this.size-1까지로 지정
            this.elements[i] = this.elements[i+1];
        }
        this.size--;
        return true; // 여기까지 오면, 삭제가 정상적으로 이뤄진 것이므로 true 반환
    }

    // element의 인덱스로 접근을 해서 데이터를 가져오는 메소드
    @Override
    public T get(int index) {
        if (index < 0 || index > this.size - 1) { // (this.size <= index)
            throw new IndexOutOfBoundsException();
        }
        return this.elements[index];
    }

    // 데이터가 있는지 없는지 뿐만 아니라,
    // 데이터가 있으면 어느 위치의 index에 존재하는지, 그 index 위치 찾아서 반환
    @Override
    public int indexOf(T t) {
        for (int i=0; i<this.size; i++) {
            if (this.elements[i].equals(t)) { // elements[i]가 t와 동일하다면,
                return i; // index값 반환
            }
        }
        return -1; // 끝까지, 찾지 못한 경우 -1 리턴
    }

    @Override
    public boolean isEmpty() {
        return this.size == 0;
    }

    // parameter(매개변수)로 받은 데이터 t가 우리가 구현한 MyArrayList안에 존재하는지 확인해서,
    // 데이터가 있으면 true, 없으면 false 반환
    @Override
    public boolean contains(T t) {
        for (int i=0; i<this.size; i++) {
            if (this.elements[i].equals(t)) { // elements[i]가 t와 동일하다면,
                return true;
            }
        }
        return false;
    }
// contains 함수의 가능한 다른 답안
//    @Override
//    public boolean contains(T t) {
//        for(T elem : this.elements) { // for-each문
//            if (elem.equals(t)) {
//                return true;
//            }
//        }
//        return false;
//    }

    @Override
    public int size() {
        return this.size;
    }
}

03. 연결 리스트

LinkedList

LinkedList는 Node라는 객체로 구성되어있다.
Node는 데이터를 저장할 수 있는 필드와 다음 노드를 가리키는 ‘next point a field’를 가지게 되고, 이 노드들이 모두 연결된 형태를 ‘링크드 리스트(LinkedList)’ 라고 한다.

여기서 가장 앞에 위치한 노드는 ‘Head’ 라고 하고,
가장 끝에 위치한 노드를 ‘Tail’ 이라고 한다. Tail은 자신이 가리킬 다음 노드가 없기 때문에, Tail의 next point는 Null을 가리키고 있게 된다.

검색

링크드 리스트는 Array랑 다르게, 인덱스를 통한 랜덤 엑세스가 불가능하다. 자신을 가리키고 있는 Next Pointer만을 통해서 접근을 할 수 있기 때문에, N개의 노드를 가지고 있는 링크드 리스트 검색의 시간 복잡도는 $O(N)$이다.

왜냐하면, 우리가 찾아가고자 하는 위치를 Head에서부터 Tail까지 순회하면서 데이터를 찾아나가야 하기 때문.

추가

맨 마지막인 Tail 노드의 다음에 붙인다고 가정

마찬가지로, 추가 작업도 앞에서부터 하나씩 찾아가면서 제일 끝 노드에 간 다음에, Null을 가리키고 있는 포인터에 우리가 추가하고자 하는 노드 데이터를 넣어줘야하기 때문에, 찾아가는 과정에서 $O(N)$의 시간 복잡도를 소요하게 된다.

그래서 데이터를 추가하게 되면, 최종적으로 위와 같은 형태의 링크드 리스트가 완성될 것이다.

삽입

제일 끝이 아니라 중간에 넣는다고 가정

중간에 넣을 때는 ArrayList와는 다르게 데이터를 다 밀어줄 필요는 없다.
간단하게 포인터만 바꿔주면 삽입이 되기는 하지만, 이 때 삽입하기 위해 찾아가는 과정이 $O(N)$이므로, 시간 복잡도는 $O(N)$이 된다.

넣고자하는 데이터의 위치를 기준으로 해서 해당 위치를 기준으로 이전 노드의 포인터가 자신을 가리키게 하고, 이전 노드가 가리키고 있던 Next 노드를 내가 Next 노드로 가지게 되면, 위 그림과 같은 연결이 완성될 것이다. 이런식으로 삽입이 이루어지게 된다.

삽입을 할 때, 뒤나 중간이 아닌 위와 같이 Head에만 삽입하는 경우가 있을 수도 있다.
만약에 Array에서 무조건 0번째에 데이터를 넣는다고 하면, 전체 데이터를 모두 한 번씩 뒤로 옮겨야 하기 때문에, 무조건 N번의 수행이 발생할 수 밖에 없으므로 매우 비효율적이다.

근데, 링크드 리스트 같은 경우에는 가장 앞에 넣는 경우 Head의 포인터만 설정을 해주면 되기 때문에, 오히려 간단하다.

삭제

링크드 리스트에서 중간에 삭제하고자 하는 노드가 있다면, 이 노드를 찾아가는 과정은 마찬가지로 $O(N)$일 것이다. 근데, 이 때 링크드 리스트의 삭제에서는 (Array와 다르게 추가적으로 $O(N)$이 소요되는, 삭제하고 데이터들을 옮겨주는 작업이 필요없이) 포인터만 조금 바꿔주면 데이터의 삭제가 이뤄지게 된다.

우리가 삭제하고자 하는 노드를 기준으로 해서 해당 노드의 이전 노드가 자신을 가리키는 것이 아니라, 자신이 가리키고 있던 Next 노드를 가리키게 한다.

그리고, 자신의 Next는 아무것도 가리키지 않게 될 것이다.

자바에서는, 아무것도 참조하지 않는 해당 객체를 가비지 컬렉터가 수거해가면서 자동으로 삭제가 이뤄지게 된다.

장점

• 배열의 복사나 재할당없이 데이터 추가 가능
• 유연한 공간

단점

• 데이터 접근에 대한 시간이 늘어남

LinkedList vs Array

	LinkedList	Array
추가	$O(N)$	$O(1)$, $O(N)$
삽입	$O(N)$	$O(N)$
삭제	$O(1)$	$O(N)$
검색	$O(N)$	$O(1)$

• 추가 → 데이터를 제일 뒤에 붙이는 추가 작업

  • LinkedList의 경우에는 데이터를 하나씩 찾아가기 때문에, $O(N)$

  • Array의 경우에는 인덱스를 통해서 데이터를 찾아가서 추가를 하기 때문에, 제일 뒤에 있는 데이터를 찾아가기 위해 다 끝까지 순회할 필요가 없으므로 $O(1)$의 시간 복잡도를 갖는다.

    • 배열이 꽉 차있는 경우에 배열의 사이즈를 재할당해서 데이터를 옮기는 과정이 있기 때문에, 이런 경우에는 $O(N)$까지 시간복잡도가 늘어날 수 있음.

    • 링크드 리스트 같은 경우는 데이터를 제일 앞에다 넣는 경우 무조건 $O(1)$의 시간 복잡도를 갖는다.

04~05. 연결 리스트 구현

main > java > list > IList.java

package list;

public interface IList<T> {
    
    void add(T t);

    void insert(int index, T t);

    void clear();

    boolean delete(T t);

    boolean deleteByIndex(int index);

    T get(int index);

    int indexOf(T t);

    boolean isEmpty();

    boolean contains(T t);

    int size();

}

링크드 리스트를 구현을 할 때는 Dummy node라는 개념을 써서 링크드 리스트를 구현한다.

Dummy node는 링크드 리스트가 존재할 때 Head는 어떠한 상황에서도 빈 상태로 있기 때문에, 링크드 리스트에 아무 데이터를 넣지 않은 상황이어도 Head node는 미리 이미 존재하고 있는 상황이고, Head에는 데이터를 넣을 수 없는 상황이다. (Head 다음부터 데이터를 넣는 것이다)

이렇게 하면, 코드의 구현에 있어서 좀 더 간결해진다는 장점이 있다. (if문으로 일일히 조건을 정의해줄 필요가 없어지기 때문)

main > java > list > MyLinkedList.java

package list;

public class MyLinkedList<T> implements IList<T> {

    // 2.
    private int size;
    private Node head;

    // 3. MyLinkedList의 생성자
    public MyLinkedList() {
        this.size = 0;
        this.head = new Node(null); // dummy head node
    }
    // 4. 추가 함수
    @Override
    public void add(T t) {
        Node current = this.head;
        while (current.next != null) {
            current = current.next;
        } // current.next가 null이라는 것은 그 다음이 없다는 것이므로,
          // 그 다음에 내 데이터가 없을 때까지 쭉 노드를 타고 들어가는 작업을 의미
        Node node = new Node(t);
        current.next = node;
        this.size++;
    }
    // 5. 삽입 함수 (Array와 달리 포인터 몇개만 바꿔주는걸로 insert 작업 가능)
    @Override
    public void insert(int index, T t) {
        if (index > this.size || index < 0) { // (index >= this.size || index < 0) 이렇게 this.size와 동일한 값이 들어오면,
            // add 메소드랑 똑같은 작업을 하게 되므로 위와 같이 조건을 정의한다.
            throw new IndexOutOfBoundsException();
        }

        Node prev = this.head; // 이전 노드 : prev
        Node current = prev.next;

        int i = 0;
        while (i++ < index) { // index까지 while문 실행
            prev = prev.next;
            current = current.next;
        } // index의 위치까지 하나씩 옮겨가면서 이동
        // i가 index의 위치까지 가게되면,
        Node newNode = new Node(t, current); // 새로 만들어진 노드는 중간에 들어가는 것이기 때문에, 이 노드의 next는 current를 가리키고,
        prev.next = newNode; // 새로 만들어진 노드가 이전꺼의 다음꺼가 되도록
        this.size++;
    }

    // 6. LinkedList에 있는 데이터를 모두 비워주는 메소드
    @Override
    public void clear() {
        this.size = 0;
        this.head.next = null; // this.head.next가 null을 가리키게 되면, 노드의 연결이 끊어지게 되면서 데이터들 비워짐
    }

    // 7. 파라미터로 받은 데이터 t가 위치한 노드를 찾아서 그 노드를 지워주는 메소드
    @Override
    public boolean delete(T t) {
        Node prev = this.head;
        Node current = prev.next;
        while (current != null) { // 처음부터 끝까지 순환
            if (current.data.equals(t)) { // 여기에 걸리면 current 노드는 우리가 지워야 할 target이 되는 노드
                prev.next = current.next;
                current.next = null; // 우리가 지우고자 하는 노드는 next로 아무 것도 가리키지 않게
                this.size--;
                return true; // 삭제가 정상적으로 완료되었다는 의미로 true 리턴
            }
            prev = prev.next;
            current = current.next;
        }
        return false;
    }

    // 8. index와 일치하는 데이터 찾은 후, 해당 데이터 삭제
    @Override
    public boolean deleteByIndex(int index) {
        if (index >= this.size || index < 0) {
            throw new IndexOutOfBoundsException();
        } // index가 잘못 들어올 경우에 대한 예외처리

        Node prev = this.head;
        Node current = prev.next;

        int i = 0;
        while (i++ < index) {
            prev = prev.next;
            current = current.next;
        } // 우리가 목표로 하는 index의 위치까지 하나씩 타고 들어감

        prev.next = current.next;
        current.next = null;
        this.size--;
        return true;
    }

    // 9. index와 일치하는 노드에 들어있는 데이터를 가져오는 메소드
    @Override
    public T get(int index) {
        if (index >= this.size || index < 0) {
            throw new IndexOutOfBoundsException();
        } // index가 잘못 들어올 경우에 대한 예외처리

        Node current = this.head.next; // head를 dummy node로 사용하기 때문에, 굳이 head부터 볼 필요는 없다
        // head의 next가 처음 데이터가 들어있는 위치이기 때문에, this.head.next부터 데이터 탐색 시작
        int i = 0;
        while (i++ < index) {
            current = current.next;
        }
        return current.data;
//        // this.head부터 시작하고 싶다면 아래와 같이..
//        Node current = this.head;
//        int i = -1; // 왜냐하면, head는 실제로 데이터가 들어있는 부분이 아니므로 -1부터 시작
//        while (i++ < index) {
//            current = current.next;
//        }
//        return current.data;
//        }
    }

    // 10. 파라미터로 받은 데이터 t가 있는 노드의 index를 반환
    @Override
    public int indexOf(T t) {
        Node current = this.head.next;
        int index = 0;
        while (current != null) { // 처음부터 끝까지 돌거임
            if (current.data != null && current.data.equals(t)) {
                return index;
            }
            current = current.next;
            index++; // 노드 한 칸 옮길 때마다 index도 같이 갱신
        }
        return -1;
    }

    // 11. 비어있는지 확인
    @Override
    public boolean isEmpty() {
        return this.head.next == null; // LinkedList스럽게 null여부로 체크
    }

    // 12. 파라미터로 넘겨 받은 데이터 t가 LinkedList에 포함되어있는지 확인
    @Override
    public boolean contains(T t) {
        Node current = this.head.next; // 노드의 연결을 변경해줄 필요가 없으니까 current만 가지고 진행
        while (current != null) {
            if (current.data != null && current.data.equals(t)) {
                return true;
            }
            current = current.next;
        }
        return false;
    }

    // 13. 사이즈 확인하는 함수
    @Override
    public int size() {
        return this.size;
    }

    // 1. Node 클래스
    private class Node {
        T data; // 데이터를 담을 수 있는 필드
        Node next; // 다음 Node를 가리키고 있는 포인터 next

        // 생성자
        Node(T data) {
            this.data = data;
        }
        // 생성자
        Node(T data, Node next) {
            this.data = data;
            this.next = next;
        }
    }
}

06~07. 이중 연결 리스트 (Double Linked List)

DoubleLinkedList

Double Linked List를 그림으로 나타내면 위와 같은 모양이다.

일반 Linked List에서는 HEAD 노드를 가지고, 하나씩 찾아 들어가는 구조였다.

Double Linked List에서는 HEAD 노드와 TAIL 노드를 각각 따로 가지고 있게 된다.

NEXT 포인터 뿐만 아니라 이전 노드를 가리키고 있는 PREV 포인터 함께 가지고 있다.

Double Linked List에서도 Single Linked List와 마찬가지로 dummy node를 사용한 구현을 할 것이다. Double Linked List가 처음 초기화 됐고, 아무 데이터도 들어오지 않은 상태라면 위 그림과 같이 HEAD 더미와 TAIL 더미 노드를 하나씩 각각 가지고 있을 것이다.

그리고, HEAD의 Next는 TAIL을 가리키고, TAIL의 Prev는 HEAD를 가리키고 있는 모양이 나온다.

Double Linked List에 실제로 데이터가 들어오면, 위 그림과 같은 모양이 될 것이다.
데이터 노드는 더미 노드인 HEAD와 TAIL노드 사이에 각각 위치한다.
실질적으로, 가장 앞에 있게 되는 데이터 노드는 더미 노드인 HEAD의 다음 노드가 될 것이고, 가장 마지막에 있는 데이터 노드는 더미 노드인 TAIL 노드의 바로 앞에 있는 노드가 될 것이다.

추가

데이터를 가장 마지막 노드에 추가해줘야 한다면, 위 그림과 같이 TAIL 더미 노드의 바로 앞 노드에 데이터를 삽입해주면 된다.

Double Linked List에서는 TAIL 노드를 가지고 있기 때문에, TAIL을 기준으로 가장 마지막 노드를 찾아서 거기에다가 데이터를 추가해주기만 하면 된다.

Double Linked List에 데이터가 수 천, 수 백개가 들어있어도 언제나 TAIL 통해서 한번에 찾아갈 수 있기 때문에 시간 복잡도는 $O(1)$을 가지게 된다.

index를 통한 접근 (검색)

배열은 인덱스를 통해 한 번에 접근 가능, Single Linked List 경우에는 HEAD를 통해 타고 들어가는 방식으로 접근, Double Linked List는 Single Linked List와 마찬가지로 노드 연결을 타고 들어가는 방식으로 접근이 가능.

예를 들어, 위 그림과 같이 4개의 데이터가 들어있는 Double Linked List를 가정했을 때, 1번째 인덱스에 있는 데이터를 가져 오고자 한다면,

앞쪽부터, Next 포인터로 이동을 하면서 index의 위치까지 이동해서 데이터를 가져올 수 있다. 여기까지 Single Linked List와의 차이점은 없어보이지만,

만약에 3번째 인덱스에 위치한 데이터를 가져온다고 하면, Double Linked List는 TAIL을 가지고 있기 때문에, HEAD가 아닌 TAIL에서부터 Prev 노드를 통해 이동해서 데이터를 가져오는 다소 효율적인 접근을 할 수 있다.

Double Linked List에서는 절반을 나눈 포인트를 기준으로해서 HEAD에서 가까우면 HEAD를 통해서, TAIL에서 가까우면 TAIL부터 접근해서 데이터를 가져올 수 있게 된다.

데이터가 만약 10개가 들어있다면 최대 5번의 탐색을 통해서 데이터를 가져올 수 있게 된다.

즉, N개의 데이터가 들어있다면 $\frac{N}{2}$번의 탐색을 통해서 데이터에 접근을 할 수 있게 되는 것이다.

시간 복잡도로 표현하면, 접근 표기법의 특징에 따라 상수항인 $\frac{N}{2}$은 날려버리기 때문에 표기시에는 단순하게 $O(N)$으로 표현한다.

Single Linked List일 때와 비교하면 시간 복잡도가 동일한 $O(N)$으로 표현하기는 하지만, 실제 연산 소요시간은 Double Linked List가 절반 정도 더 짧을 것으로 예상해볼 수 있다.

index를 통한 삽입

index를 통해 위치를 찾아가는 것은 index를 통한 접근 (검색) 부분에 내용 있음.

위 그림 상에 curr이 가리키는 위치가 우리가 데이터를 삽입하고자 하는 index의 위치라고 가정해보자.

그리고, 그 위치에다가 새로 삽입될 데이터가 있는 new Node() 데이터를 넣어줄 것이다.

방금 생성한 new Node()는 현재 curr이 가리키고 있는 노드의 이전 노드를 자신의 이전 노드로 가지고, 현재 curr이 가리키고 있는 노드는 자신의 Next 노드로 가져야지 new Node()가 현재 인덱스 위치에 삽입이 될 것이다.

그 다음으로 현재 curr이 가리키고 있는 노드와 curr의 기존의 Prev였던 노드 간의 연결을 정리해주는 작업을 해준다.

그래서, curr앞에 있던 prev노드는 Next 노드로 curr이 아니라 우리가 새로 생성한 노드를 가리키면 될 것이고, curr노드는 Prev 포인터로 기존의 prev가 아닌 새로 생성한 노드(new Node)를 가리키게 바꿔준다.

Double Linked List에 데이터가 삽입이 되면 기존의 prev와 curr사이에 우리가 생성해준 new Node가 위 그림과 같이 들어간 모양이 완성이 되야한다.

중간에 연결이 잘못되거나 끊기면 더 이상 next나 prev로는 이동을 할 수 밖에 없기 때문에, 그 이후의 데이터나 그 이전의 데이터가 모두 날아가버릴 수 있다. 그래서, LinkedList에선 연결을 잘 맺어주는게 굉장히 중요하다.

index를 통한 삭제

인덱스로 들어오는 과정은 위 내용들과 동일하다.

위 그림과 같이, 우리가 삭제할 target 노드(초록색)를 기준으로 이전 노드인 prev 노드와 다음 노드인 next 노드인 연결해주는 작업을 한다. prev의 Next 포인터는 curr의 next를 가리키게 하고, next 노드는 Prev 포인터로 curr이 아닌 curr의 prev를 가리키게 한다.

그리고, curr에서 연결되고 있던 것들은 모두 끊어준다.

결과적으로는 위와 같은 모양이 나올 것이다.

08~09. 이중 연결 리스트 구현

main > java > list > MyDoubleLinkedList.java

package list;

public class MyDoubleLinkedList<T> implements IList<T> {
    // 2.
    private Node head;
    private Node tail;
    private int size;

    // 위 멤버 변수들을 초기화해주는 생성자 작성
    public MyDoubleLinkedList() {
        this.size = 0;
        this.head = new Node(null); // dummy node
        this.tail = new Node(null); // dummy node
        this.head.next = this.tail;
        this.tail.prev = this.head;
        // size()
        // clear()
        // add()
    }

    // 5. 추가
    @Override
    public void add(T t) {
        Node last = this.tail.prev; // this.tail.prev가 가리키고 있는게 마지막 노드 last
        Node newNode = new Node(t, last, tail); // 새로운 노드는 데이터 t를 가지고, last노드를 자신의 prev로, tail을 자신의 next노드로 가짐
        last.next = newNode; // last의 next는 새로운 노드를 가리키게
        this.tail.prev = newNode; // tail노드의 prev도 새로 생성한 노드를 가리키게
        this.size++;

        // 그 다음 get(index)
    }

    // 7. 삽입
    @Override
    public void insert(int index, T t) {
        if (index > this.size || index < 0) {
            throw new IndexOutOfBoundsException();
        }

        Node prev = null;
        Node current = null;
        int i = 0;

        if (index < this.size / 2) { // index가 head에서 더 가까운 경우
            prev = this.head;
            current = this.head.next;
            while (i++ < index) {
                prev = prev.next;
                current = current.next;
            }
        } else { // index가 tail에서 더 가까운 경우
            current = this.tail;
            prev = this.tail.prev;
            while (i++ < (this.size - index)) {
                current = current.prev;
                prev = prev.prev;
            }
        }
        Node newNode = new Node(t, prev, current);
        current.prev = newNode;
        prev.next = newNode;
        this.size++;
        // 그 다음 delete by index
    }

    // 4. Double Linked List에 아무 데이터도 들어오지 않은 상태로 초기화하는 메소드
    @Override
    public void clear() {
        this.size = 0;
        this.head.next = this.tail;
        this.head.prev = null;
        this.tail.next = null;
        this.tail.prev = this.head;
    }

    @Override
    public boolean delete(T t) {
        Node prev = this.head;
        Node current = prev.next;
        while (current != null) {
            if (current.data.equals(t)) {
                prev.next = current.next;
                current.next.prev = prev;
                current.next = null;
                current.prev = null;
                this.size--;
                return true;
            }
            prev = prev.next;
            current = current.next;
        }
        return false;
    }

    // 8. index를 통한 삭제
    @Override
    public boolean deleteByIndex(int index) {
        if (index >= this.size || index < 0) {
            throw new IndexOutOfBoundsException();
        }

        Node prev = null;
        Node current = null;
        Node next = null;

        int i = 0;
        if (index < this.size / 2) { // index가 헤드에서 더 가까우면
            prev = this.head;
            current = this.head.next;
            while (i++ < index) {
                prev = prev.next;
                current = current.next;
            } // 이 while문이 종료되면, current노드 :: 우리가 지우고 싶어하는 index의 위치가 들어있을 것임
            prev.next = current.next; // prev.next가 원래는 current를 가리키고 있었을 것이므로, current의 next를 가리키도록 바꿔줌
            current.next.prev = prev; // current.next의 prev포인터는 원래 current를 가리키고 있었으므로, prev를 가리키도록 변경
            current.next = null;
            current.prev = null;
        } else { 
            // tail에서 역으로 찾아가는 경우
            current = this.tail.prev;
            next = this.tail;
            while (i++ < (this.size - index - 1)) {
                next = next.prev;
                current = current.prev;
            } // 이 while문이 종료되면, next는 우리가 지우고자 하는 current의 다음 노드,
            next.prev = current.prev; // 이 노드의 이전 노드는 원래 current를 가리키고 있었으므로, current보다 1칸 앞에 있는 current.prev를 가리키도록
            current.prev.next = next; // current의 prev의 next포인터는 원래 current를 가리키고 있었으므로, next를 가리키도록
            current.next = null;
            current.prev = null;
        }
        this.size--;
        return true;
    }

    // 6. index 접근을 해서 데이터 가져오는 메소드
    @Override
    public T get(int index) {
        if (index >= this.size || index < 0) {
            throw new IndexOutOfBoundsException();
        } // 잘못된 인덱스가 들어온 경우에 대한 예외처리

        int i = 0;
        Node current = null;
        if (index < this.size / 2) { // index가 헤드에서 더 가까우면
            current = this.head.next;
            while (i++ < index) {
                current = current.next;
            }
        } else { // index가 tail에서 더 가까운 경우
            current = this.tail.prev;
            while (i++ < (this.size - index - 1)) { // 여기서는 index가 역순으로 가니까
                current = current.prev;
            }
        }
        return current.data;
        // 그 다음 insert(index)
    }

    @Override
    public int indexOf(T t) {
        Node current = this.head.next;
        int index = 0;
        while (current != null) {
            if (current.data != null && current.data.equals(t)) {
                return index;
            }
            current = current.next;
            index++;
        }
        return -1;
    }

    @Override
    public boolean isEmpty() {
        return this.head.next == this.tail;
    }

    // 9.
    @Override
    public boolean contains(T t) { // O(N) -> O(N/2)
        Node current = this.head.next;
        while (current != null) {
            if (current.data != null && current.data.equals(t)) {
                return true;
            }
            current = current.next;
        }
        return false;
    }

    // 3.
    @Override
    public int size() {
        return this.size;
    }

    // 1. 노드 기반으로 구현하기 때문에, 아래와 같이 내부 클래스 생성
    private class Node {
        T data;
        Node prev;
        Node next;

        Node(T data) {
            this.data = data;
        }

        Node(T data, Node prev, Node next) {
            this.data = data;
            this.prev = prev;
            this.next = next;
        }
    }
}

🔊 캡쳐 이미지는 패스트캠퍼스(Fast Campus) 소유이므로, 무단 불펌하지 말아주세요!

맨 위로 이동하기