[자료구조] 리스트 - LinkedList

Linked List 장점

  - 배열의 복사나 재할당없이 데이터 추가 가능

  - 유연한 공간

Linked List 단점

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

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

 

LinkedList 예제

1. 우선 LinkedList는 Node를 기반으로 하기 때문에 Node를 먼저 생성

private class Node {
        T data;
        Node next;

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

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

 

2. 초기설정 및 생성자 생성

package list;

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

    private int size;
    private Node head;

    public MyLinkedList() {
        this.size = 0;
        this.head = new Node(null); // dummy head node
    }

 

3. 배열 끝에 데이터를 넣어주는 add 함수 예제

@Override
    public void add(T t) {
        Node curr = this.head;
        while (curr.next != null) {
            curr = curr.next;
        }
        Node node = new Node(t);
        curr.next = node;
        this.size++;
    }

 

4. 배열의 원하는 부분에 데이터를 넣어주는 insert함수 예제

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

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

        int i = 0;
        while (i++ < index) {
            prev = prev.next;
            curr = curr.next;
        }

        Node node = new Node(t, curr);
        prev.next = node;
        this.size++;
    }

 

5. 배열에 데이터를 전부 비워주는 clear함수 예제

@Override
    public void clear() {
        this.size = 0;
        this.head.next = null;
    }

 

6. 배열의 삭제하고 싶은 데이터(원하는 값)을 삭제하는 delets함수 예제

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

 

7. 배열의 위치에 해당하는 데이터를 삭제하는 deleteByIndex함수 예제

@Override
    public boolean deleteByIndex(int index) {
        if(index >= this.size || index < 0) {
            throw new IndexOutOfBoundsException();
        }

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

        int i = 0;
        while (i++ < index) {
            prev = prev.next;
            curr = curr.next;
        }

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

 

8. index를 기반으로 배열의 원하는 데이터를 가져오는 get함수 예제

@Override
    public T get(int index) {
        Node curr = this.head.next;
        int i = 0;
        while (i++ < index) {
            curr = curr.next;
        }
        return curr.data;
    }

 

9. contains함수와 유사하지만 데이터의 유무만 파악해주는게 아닌 존재한다면 어느 위치에 존재하는지 알려주는 indexOf함수 예제

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

 

10. 배열에 데이터가 있는지 없는지 확인하는 isEmpty함수 예제

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

 

11. 파라미터 t로 받은 데이터가 배열에 존재하면 true 그렇지 않다면 false를 반환하는 contains함수 예제

@Override
    public boolean contains(T t) {
        Node curr = this.head.next;
        while (curr != null) {
            if(t.equals(curr.data)) {
                return true;
            }
            curr = curr.next;
        }
        return false;
    }

 

12. 배열에 데이터가 얼마나 있는지 조회해주는 size함수 예제

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