JAVA LinkedList 직접 구현하기 - 자료구조(3)

1. 개념

---

• 자바의 List를 상속받는 클래스 중 하나
• 노드의 연속으로 각 노드가 데이터와 다음 노드의 주소인 포인터를 가져 체인처럼 연결된 구조로 되어 있다.
• header는 첫 번째 노드를 가리키는 포인터 역할만 한다. 그 이후부터는 각 노드가 자신의 데이터와 다음 노드의 주소를 갖는다.

• 데이터가 추가 삭제되면 주소만 연결해주면 된다.

• 노드끼리 연결되어 있어 LinkedList라고 불린다.
• 앞뒤 주소 둘 다 가지고 있으면 양방향 LinkedList 즉, Double LinkedList 라 한다.

 

---

 

2. 내부 코드 까 보기

---

함수를 다 보진 않고 ArrayList의 특징을 잘 나타내는 함수 몇 개만 봐보자.

java 1.1 버전의 ArrayList를 중심으로 함수를 추려보았다.

https://docs.oracle.com/javame/config/cdc/ref-impl/pbp1.1.2/jsr217/java/util/LinkedList.html

LinkedList (Personal Basis Profile 1.1.2)

add - List에 객체 추가

addFirst

addLast

clear - List 안에 있는 내용 비우기

contains - List 안에 객체가 있는지 여부

get - List 안에 있는 국제 불러오기

getFirst

getLast

indexOf - 첫 번째 객체의 있는지

lastIndexOf - 마지막 객체의 인덱스

remove - 객체 삭제

removeFirst

removeLast

set - 인덱스 번째로 객체 세팅

size

toArray - array 반환

 

 

---

 

3. 직접 구현

---

대표적인 함수를 직접 구현하고 해당 기능이 정상적으로 돌아가는데 테스트 케이스를 생성하였다.

내가 만든 MyLinkedList코드 와 이를 확인 하는 테스트코드 이다

package List;

import java.util.NoSuchElementException;

public class MyLinkedList<E> {
    private int size;
    private Node<E> first;
    private Node<E> last;

    public void add(int index, E element){
        checkIndexRange(index);
        if(index == 0){
            addFirst(element);
            return;
        }else if(index == size){
            addLast(element);
            return;
        }
        Node<E> indexNode = node(index);
        Node<E> prevNode = indexNode.prev;

        Node<E> newNode = new Node<>(prevNode, element, indexNode);
        prevNode.next = newNode;
        indexNode.prev = newNode;
        size++;
    }

    public boolean add(E element){
        addLast(element);
        return true;
    }

    public void addFirst(E element){
        Node<E> oldFirst = first;
        Node<E> newNode = new Node<E>(null, element ,first);
        first = newNode;

        if(oldFirst == null){
            last = newNode;
        }else{
            oldFirst.prev = newNode;
        }
        size++;
    }

    public void addLast(E element){
        Node<E> oldLast = last;
        Node<E> newNode = new Node<E>(last, element,null);
        last = newNode;

        if(oldLast == null){
            first = newNode;
        }else {
            oldLast.next = newNode;
        }
        size++;

    }

    public void clear(){
        first = null;
        last = null;
        size = 0;

    }

    public E get(int index){
        checkIndexRange(index);
        return node(index).item;
    }

    private Node<E> node(int index) {
        Node<E> indexNode;
        if(size/2 >= index){
            indexNode = first;
            for (int i = 0; i < index; i++) {
                indexNode = indexNode.next;
            }

            return indexNode;
        }

        indexNode = last;
        for (int i = size - 1; i > index; i--) {
            indexNode = indexNode.prev;
        }

        return indexNode;
    }

    private void checkIndexRange(int index) {
        if(index >= size || index < 0) throw new IndexOutOfBoundsException();
    }

    public E getFirst(){
        checkHasElement();
        return first.item;
    }

    public E getLast(){
        checkHasElement();
        return last.item;
    }

    private void checkHasElement() {
        if(size < 1) throw new NoSuchElementException();
    }

    public int indexOf(E element){
        Node<E> indexNode = first;
        if(element == null){
            for (int i = 0; i < size; i++) {
                if(indexNode.item ==null) return i;

                indexNode = indexNode.next;
            }
        }

        for (int i = 0; i < size; i++) {
            if(element.equals(indexNode.item)) return i;
            indexNode = indexNode.next;
        }

        return -1;
    }

    public E remove(int index){
        checkIndexRange(index);
        Node<E> indexNode = node(index);
        unLink(indexNode);
        return indexNode.item;
    }

    public boolean remove(E element){
        checkHasElement();
        Node<E> indexNode = first;
        if(element == null){
            for (int i = 0; i < size; i++) {
                if(indexNode.item == null){
                    unLink(indexNode);
                    return true;
                }
                indexNode = indexNode.next;
            }
        }else{
            for (int i = 0; i < size; i++) {
                if(element.equals(indexNode.item)){
                    unLink(indexNode);
                    return true;
                }
                indexNode = indexNode.next;
            }
        }
        return false;
    }

    public E removeFirst(){
        checkHasElement();
        Node<E> firstNode = first;
        unLink(firstNode);
        return firstNode.item;
    }

    public E removeLast(){
        checkHasElement();
        Node<E> lastNode = last;
        unLink(lastNode);
        return lastNode.item;
    }

    public E set(int index, E element){
        checkIndexRange(index);
        Node<E> indexNode = node(index);
        E originElement = indexNode.item;
        indexNode.item = element;

        return originElement;
    }

    public int size(){
        return size;
    }

    private void unLink(Node<E> node) {

        Node<E> nextNode = node.next;
        Node<E> prevNode = node.prev;

        if(nextNode == null){
            last = node.prev;
        }else{
            nextNode.prev = prevNode;
        }

        if(prevNode == null){
            first = node.next;
        }else {
            prevNode.next = nextNode;
        }

        size--;
    }

    private static class Node<E>{
        E item;
        Node<E> next;
        Node<E> prev;

        Node(Node<E> prev, E element, Node<E> next){
            this.prev = prev;
            this.item = element;
            this.next = next;
        }
    }

}

---

자료구조 시리즈

1. 자료구조의 종류와 개념 - 자료구조(1)

2. JAVA ArrayList - 자료구조(2)

3. JAVA LinkedList - 자료구조(3) 

4. JAVA ArrayList와 LinkedList 성능 비교 - 자료구조(4)

5. JAVA Queue 그리고 offer, poll , peek - 자료구조(5)

6. JAVA 왜 Stack 은 Array로, Queue는 LinkedList로 구현 했을까? - 자료구조(6)

7. JAVA Hash 그리고 HashMap 과 HashTable - 자료구조(7)

8. JAVA HashMap 과 HashSet의 성능 비교 - 자료구조(8)

9. JAVA HashMap의 용량은 왜 2의 거듭제곱일까? - 자료구조(9)