[알고리즘/JAVA] 자료구조 - 시간복잡도(queue, stack, arraylist, linkedlist)

 

자료구조별 시간복잡도

자료구조	접근	탐색	삽입	삭제	특징
배열	O(1)	O(n)	O(n)	O(n)	접근이 빠르다
스택	O(n)	O(n)	O(1)	O(1)	삽입과 삭제가 빠르다
큐	O(n)	O(n)	O(1)	O(1)	삽입과 삭제가 빠르다
이중 연결 리스트	O(n)	O(n)	O(1)	O(1)	삽입과 삭제가 빠르다
해시 테이블	O(1)	O(1)	O(1)	O(1)	모두 빠름
이진 탐색 트리	O(logn)	O(logn)	O(logn)	O(logn)	해시보다 느리지만 모두 빠름

---

Linked List와 Array List 차이

	ArrayList	LinkedList
get / set	O(1)	O(n)
add(시작)	O(n)	O(1)
add(끝)	O(1)	O(1)
add(일반)	O(n)	O(n)
remove(시작)	O(n)	O(1)
remove(끝)	O(1)	O(1)
remove(일반)	O(n)	O(n)

 

	ArrayList	LinkedList
장점	무작위 접근 가능	빠른 자료 삽입, 삭제 자유로운 크기 조절
단점	느린 자료 삽입, 삭제 크기 조절 불가능	순차 접근만 가능

 

Linked List 개념 설명 및 종류

데이터가 자료의 주소 값으로 서로 연결(Link)되어 있는 구조

1) 단순 연결 리스트 (Singly Linked List)

각 노드에서 단방향으로 연결되는 리스트
후행 노드는 쉽게 접근 가능하지만, 선행 노드 접근이 복잡한 단점 존재

2) 이중 연결 리스트 (Doubly Linked List)

각 노드에서 양방향(선행, 후행)으로 연결되는 리스트
양 방향 접근이 용이하지만, 메모리를 추가적으로 사용

 

Linked List 직접 구현

static class Node{
        int data;
        Node next;
        public Node(int data){
            this.data = data;
            this.next = null;
        }
    }
    static class LinkedList{
        Node head;
        Node tail;
        Node[] arr;
        int count;

        public LinkedList(){
            arr = new Node[2000];
        }

        Node getNewNode(int data){
            arr[count] = new Node(data);
            return arr[count++];
        }

        void addLast(int data){
            Node curr = tail;
            Node create = getNewNode(data);
            if(tail==null){
                head = create;
                tail = create;
                return;
            }
            curr.next = create;
            tail = create;
        }

        void insert(int index, int data){
            Node create = getNewNode(data);
            if(index == 0){
                if(head!=null){
                    create.next = head;
                }
                head = create;
            }
            else{
                Node curr = head;
                for(int i=1; i<index; i++){
                    curr = curr.next;
                }
                create.next = curr.next;
                curr.next = create;
            }
            if(create.next==null) tail = create;
        }

        void delete(int index){
            Node curr = head;
            if(index==0){
                head = curr.next;
                return;
            }
            for(int i=1; i<index; i++){
                curr = curr.next;
            }
            Node target = curr.next;
            curr.next = target.next;
            if(curr.next==null) tail = curr;
        }

        void update(int index, int data){
            Node curr = head;
            for(int i=1; i<=index; i++){
                curr = curr.next;
            }
            curr.data = data;

        }

        int get(int index){
            Node curr = head;
            for(int i=1; i<=index; i++){
                if(curr==null) return -1;
                curr = curr.next;
            }
            return curr.data;
        }
    }