[자료구조] 연결리스트 (LinkedList) / 배열리스트 (ArrayList)

LinkedList (연결리스트)

■ 정의

- LinkedList (연결리스트)는 각 노드가 데이터와 포인터를 가지고 한 줄로 연결되어 있는 방식으로 데이터를 저장하는 자료구조
- 각 노드의 포인터 변수는 다음 노드의 데이터의 주소를 값을 가지고 각 포인터 변수의 주소도 따로 존재

 

■ 생성자

- LinkedList<Integer> list = new LinkedList<>();

 

■ Code

import java.util.Comparator;

public class LinkedList<E> {
    class Node<E> {
        private E data;
        private Node<E> next;
        Node(E data, Node<E> next) {
            this.data = data;
            this.next = next;
        }
    }

    private Node<E> head;
    private Node<E> crnt;

    public LinkedList() {
        head = crnt = null;
    }

    public E search(E obj, Comparator<? super E> c) {
        Node<E> ptr = head;

        while (ptr != null) {
            if (c.compare(obj, ptr.data) == 0) {
                crnt = ptr;
                return ptr.data;
            }
                ptr = ptr.next;
        }
            return null;
    }

    public void addFirst(E obj){
        Node<E> ptr = head;
        head = crnt = new Node<E>(obj, ptr);
    }

    public void addLast(E obj){
        if(head == null)
            addFirst(obj);

        else{
            Node<E> ptr = head;
            while(ptr.next != null)
                ptr = ptr.next;
            ptr.next = crnt = new Node<E>(obj, null);
        }
    }

    public void removeFirst(){
        if(head != null)
            head = crnt = head.next;
    }

    public void removeLast(){
        if(head != null){
            if(head.next == null)
                removeFirst();
            else{
                Node<E> ptr = head;
                Node<E> pre = head;

                while(ptr.next != null){
                    pre = ptr;
                    ptr = ptr.next;
                }
                pre.next = null;
                crnt = pre;
            }
        }
    }

    public void remove(Node p){
        if(head != null){
            if(p == head)
                removeFirst();
            else{
                Node<E> ptr = head;

                while(ptr.next != p){
                    ptr = ptr.next;
                    if(ptr == null)
                        return;
                }
                ptr.next = p.next;
                crnt = ptr;
            }
        }
    }

    public void removeCurrentNode(){
        remove(crnt);
    }

    public void clear(){
        while(head != null)
            removeFirst();
        crnt = null;
    }

    public boolean next(){
        if(crnt == null || crnt.next == null)
            return false;
        crnt = crnt.next;
        return true;
    }

    public void printCurrentNode(){
        if(crnt == null)
            System.out.println("선택한 노드가 없습니다.");
        else
            System.out.println(crnt.data);
    }

    public void dump(){
        Node<E> ptr = head;

        while(ptr != null){
            System.out.println(ptr.data);
            ptr = ptr.next;
        }
    }
}

 

■ 메소드 

메소드	의미
addFirst(int item)	리스트의 앞 쪽에 item 삽입, 용량 초과 시 예외 발생
offerFirst(int item)	리스트의 앞 쪽에 item 삽입, 용량 초과 시 false 리턴
addLast(int item)	리스트의 뒤 쪽에 item 삽입, 용량 초과 시 예외 발생
offerLast(int item)	리스트의 뒤 쪽에 item 삽입, 용량 초과 시 false 리턴
removeFirst()	리스트의 앞 쪽에 item 삭제, 리스트이 비어 있을 시 예외 발생
pollFirst()	리스트의 앞 쪽에 item 삭제, 리스트이 비어 있을 시 false 리턴
removeLast()	리스트의 뒤 쪽에 item 삭제, 리스트이 비어 있을 시 예외 발생
pollLast()	리스트의 뒤 쪽에 item 삭제, 리스트이 비어 있을 시 false 리턴
getFirst()	리스트의 맨 앞의 item을 제거하지 않은 채 리턴, 리스트이 비어 있을 시 예외 발생
peekFirst()	리스트의 맨 앞의 item을 제거하지 않은 채 리턴, 리스트이 비어 있을 시 null 리턴
getLast()	리스트의 맨 뒤의 item을 제거하지 않은 채 리턴, 리스트이 비어 있을 시 예외 발생
peekLast()	리스트의 맨 뒤의 item을 제거하지 않은 채 리턴, 리스트이 비어 있을 시 null 리턴

 

---

ArrayList

■ 정의

- ArrayList는 List 인터페이스를 상속받은 클래스로 크기가 가변적으로 변하는 선형리스트
- 한번 생성되면 크기가 변하지 않는 배열과는 달리 ArrayList는 객체들이 추가되어 저장 용량(capacity)을 초과한다면 자동으로 부족한 크기만큼 저장 용량(capacity)이 늘어남

 

■ 생성자 

- ArrayList<Integer> arr = new ArrayList<>();
- ArrayList<Integer> arr = newArrayList<>(10);                    // capacity = 10
- ArrayList<Integer> arr = newArrayList<>(Arrays.asList(1, 2, 3, 4, 5));       

 

■ Code

import java.util.Comparator;

public class ArrayLinkedList<E>{

    class Node<E>{
        private E data;
        private int next;
        private int dnext;

        void set(E data, int next){
            this.data = data;
            this.next = next;
        }
    }

    private Node<E>[] n;
    private int size;
    private int max;
    private int head;
    private int crnt;
    private int deleted;
    private static final int NULL = -1;

    public ArrayLinkedList(int capacity){
        head = crnt = max = deleted = NULL;
        try{
            n = new Node[capacity];
            for(int i = 0; i < capacity; i++)
                n[i] = new Node<E>();
            size = capacity;
        }
        catch (OutOfMemoryError e){
            size = 0;
        }
    }

    private int getInsertIndex(){
        if(deleted == NULL){
            if(max < size)
                return ++max;
            else
                return NULL;
        }else{
            int rec = deleted;
            deleted = n[rec].dnext;
            return rec;
        }
    }

    private void deleteIndex(int idx){
        if(deleted == NULL){
            deleted = idx;
            n[idx].dnext = NULL;
        }else{
            int rec = deleted;
            deleted = idx;
            n[idx].dnext = rec;
        }
    }

    public E search(E obj, Comparator<? super E> c){
        int ptr = head;

        while(ptr != NULL){
            if(c.compare(obj, n[ptr].data) == 0){
                crnt = ptr;
                return n[ptr].data;
            }
            ptr = n[ptr].next;
        }
        return null;
    }

    public void addFirst(E obj){
        int ptr = head;
        int rec = getInsertIndex();
        if(rec != NULL){
            head = crnt = rec;
            n[head].set(obj, ptr);
        }
    }

    public void addLast(E obj){
        if(head == NULL)
            addFirst(obj);
        else{
            int ptr = head;
            while(n[ptr].next != NULL)
                ptr = n[ptr].next;
            int rec = getInsertIndex();
            if(rec != NULL){
                n[ptr].next = crnt = rec;
                n[rec].set(obj, NULL);
            }
        }
    }

    public void removeFirst() {
        if (head != NULL){
            int ptr = n[head].next;
            deleteIndex(head);
            head = crnt = ptr;
        }
    }

    public void removeLast(){
        if(head != NULL){
            if(n[head].next == NULL)
                removeFirst();
            else{
                int ptr = head;
                int pre = head;

                while(n[ptr].next != NULL){
                    pre = ptr;
                    ptr = n[ptr].next;
                }
                n[pre].next = NULL;
                deleteIndex(ptr);
                crnt = pre;
            }
        }
    }

    public void remove(int p){
        if(head != NULL){
            if(p == head)
                removeFirst();
            else{
                int ptr = head;

                while(n[ptr].next != p){
                    ptr = n[ptr].next;
                    if(ptr == NULL)
                        return;
                }
                n[ptr].next = NULL;
                deleteIndex(p);
                n[ptr].next = n[p].next;
                crnt = ptr;
            }
        }
    }

    public void removeCurrentNode(){
        remove(crnt);
    }

    public void clear(){
        while(head != NULL)
            removeFirst();
        crnt = NULL;
    }

    public boolean next(){
        if(crnt == NULL || n[crnt].next == NULL)
            return false;
        crnt = n[crnt].next;
        return true;
    }

    public void printCurrentNode(){
        if(crnt == NULL)
            System.out.println("선택 노드가 없습니다.");
        else
            System.out.println(n[crnt].data);
    }

    public void dump(){
        int ptr = head;

        while (ptr != NULL){
            System.out.println(n[ptr].data);
            ptr = n[ptr].next;
        }
    }
}

 

■ 메소드

메소드	의미
add((index, val)	순서대로 리스트 추가, 사이즈 초과 시 자동으로 사이즈 증가
get(index)	해당 index 값 반환
set(index, val)	index로 값 변경
indexOf(val)	값을 제공하면 해당 값의 첫번째 index 반환
lastindexOf(val)	해당 값의 마지막 index 반환
remove(index or val)	해당 index의 값 or 해당 값 중 첫번째 값 삭제
contains(val)	해당 값이 배열에 있는지 검색 후 true / false 반환
clear()	값 모두 삭제
isEmpty()	비었으면 true, 하나라도 값이 존재하면 false 반환
addAll(arr2)	두 컬렉션을 합침
size()	요소 개수 반환

 

---

 

LinkedList vs ArrayList

 

	LinkedList	ArrayList
읽기(접근시간)	느림	빠름
추가 / 삭제	빠름	느림
비고	데이터가 많을수록 접근성이 떨어짐	순차적인 추가 / 삭제는 빠름 비효율적인 메모리 사용

- 다루고자 하는 데이터의 갯수가 변하지 않는 경우라면 ArrayList

- 데이터 갯수의 변경이 잦다면 LinkedList