Java LinkedList - 직접 구현하기 1

노드의 연결 구조로 이어진 리스트를 직접 만들어보자.
이러한 자료 구조는 연결리스트(LinkedList) 이라 불리오고 있다.

리스트 자료 구조 특징

• 중복 허용
• 데이터 순서가 있음

연결 리스트는 배열 리스트의 단점인 메모리 공간과 성능을 개선할 수 있는 자료구조이다.

배열 리스트 단점

• 동적 배열 추가로 확보한 메모리 공간 낭비
• 리스트 앞 또는 중간에서 데이터 추가 시 데이터 이동의 성능 하락

배열 리스트, 연결 리스트는 모두 같은 리스트이며 노드의 연결 구조를 사용의 차이가 있다.

CLinkedList

자료구조 연결 리스트 직접 작성해보는 시간이다.

Node.class

public class Node {
    Object item;
    Node next;

    public Node(Object item) {
        this.item = item;
    }

    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder();
        Node n = this;
        sb.append("[");
        while (n != null) {
            sb.append(n.item);
            if (n.next != null) {
                sb.append("->");
            }
            n = n.next;
        }

        sb.append("]");
        return sb.toString();
    }
}

• Node 멤버 필드와 생성자가 있다.
• toString()은 이전에 작성한 StringBuilder로 사용한다.

CLinkedList.class

public class CLinkedList {
    Node first;
    int size;

    public void add(Object e) {
        Node newNode = new Node(e);
        if (first == null) {
            // 노드를 처음으로 사용한 경우에만 수행함
            first = newNode;
        } else {
            // 노드가 있는 경우 수행
            Node lastNode = getLastNode();
            lastNode.next = newNode;
        }
        size++;
    }

    private Node getLastNode() {
        Node n = first;
        while (n.next != null) {
            n = n.next;
        }
        return n;
    }

    public Object set(int index, Object element) {
        Node n = getNode(index);
        Object oldValue = n.item;
        n.item = element;
        return oldValue;
    }

    public Object get(int index) {
        Node node = getNode(index);
        return node.item;
    }

    private Node getNode(int index) {
        Node n = first;
        for (int i = 0; i < index; i++) {
            n = n.next;
        }
        return n;
    }

    public int indexOf(Object o) {
        int index = 0;
        for (Node n = first; n != null; n = n.next) {
            if (o.equals(n.item)) {
                return index;
            }
            index++;
        }
        return -1;
    }

    public int size() {
        return size;
    }

    @Override
    public String toString() {
        return "CLinkedList{" +
                "first=" + first +
                ", size=" + size +
                '}';
    }
}

• 자바 클래스로 CLinedList 새로 작성한다.

CLinkedList 멤버 필드

Node first;
int size;

• Node 타입의 first 변수를 사용한다.
• 노드에 입력한 데이터가 몇개 인지 확인하는 size 변수를 추가한다. 데이터가 추가될 때마다 하나씩 증가한다.

add()

public void add(Object e) {
        Node newNode = new Node(e);
        if (first == null) {
            // 노드를 처음으로 사용한 경우에만 수행함
            first = newNode;
        } else {
            // 노드가 있는 경우 수행
            Node lastNode = getLastNode();
            lastNode.next = newNode;
        }
        size++;
    }

• 마지막 노드에 데이터를 추가한다.
• 노드가 없는 경우 비어있는 first 멤버 필드에 "새 노드"를 연결한다.
• 기존 노드가 있는 경우 "새 노드"를 마지막 노드에 연결한다.

set()

public Object set(int index, Object element) {
    Node n = getNode(index);
    Object oldValue = n.item;
    n.item = element;
    return oldValue;
}

• 인덱스 통해 특정 위치 데이터를 찾고 변경
• 기존에 있던 값을 반환한다.

get()

public Object get(int index) {
    Node node = getNode(index);
    return node.item;
}

• 인덱스 통해 특정 위치에 값을 반환한다.
• 조회 기능의 단점으로 getNode 루프를 돌아야한다.
  • O(1) 성능

indexOf()

public int indexOf(Object o) {
    int index = 0;
    for (Node n = first; n != null; n = n.next) {
        if (o.equals(n.item)) {
            return index;
        }
        index++;
    }
    return -1;
}

• 객체 또는 값이 있는지 확인하는 메소드

getLastNode()

private Node getLastNode() {
    Node n = first;
    while (n.next != null) {
        n = n.next;
    }
    return n;
}

• 마지막 노드 객체를 가져오기

getNode()

private Node getNode(int index) {
    Node n = first;
    for (int i = 0; i < index; i++) {
        n = n.next;
    }
    return n;
}

• 인덱스 통해 객체 노드 가져오기

size()

public int size() {
    return size;
}

• 노드의 사이즈

toString()

@Override
public String toString() {
    return "CLinkedList{" +
            "first=" + first +
            ", size=" + size +
            '}';
}

• toString() 오버라이딩으로 출력 결과를 편하게 보기

메소드와 기능 사용해보기

작성한 CLinkedList 동작하는지 엔트리 포인트를 작성한다.

Main.class

CLinkedList list = new CLinkedList();
System.out.println("** 데이터 추가하기 **");
System.out.println(list);
list.add("a");
System.out.println(list);
list.add("b");
System.out.println(list);
list.add("c");
System.out.println(list);
list.add("c");
System.out.println(list);

System.out.println("** 메소드 기능 사용하기 **");
System.out.println("list.size() = " + list.size());
System.out.println("list.get(2) = " + list.get(2));
System.out.println("list.indexOf('c') = " + list.indexOf('c'));
System.out.println("list.set(2, 'z') = " + list.set(2, 'z'));
System.out.println(list);

** 데이터 추가하기 **
CLinkedList{first=null, size=0}
CLinkedList{first=[a], size=1}
CLinkedList{first=[a->b], size=2}
CLinkedList{first=[a->b->c], size=3}
CLinkedList{first=[a->b->c->c], size=4}
** 메소드 기능 사용하기 **
list.size() = 4
list.get(2) = c
list.indexOf('c') = -1
list.set(2, 'z') = c
CLinkedList{first=[a->b->z->c], size=4}

이전에 직접 구현한 CList 메인 호출에서 객체만 바꿔줘도 모두 정상적으로 동작한다.

연결 리스트와 빅오

get()

• 특정 위치 데이터를 반환한다.
• 데이터 증가에 따른 성능 추세 빅오 O(n)
  • 배열 리스트는 원하는 데이터를 O(1) 성능으로 직접 꺼낼 수 있었다. 그렇지만 연결 리스트에 있는 노드들은 배열이 아니고 참조만 있을 뿐이다. 원하는 데이터를 찾으려면 인덱스 숫자 만큼이나 노드를 반복해서 찾는다.
  • 연결리스트는 특정 위치의 노드 반환에 O(n) 시간이 소요된다.

add()

• 마지막 노드에 데이터 추가를 강제한다.
• 데이터 증가에 따른 성능 추세 빅오 O(n)
  • 마지막 노드를 찾으므로 O(n) 이다.
  • 찾아낸 마지막 노드에 새 노드 추가에는 O(1) 이다.

int indexOf()

• 데이터 검색과 검색된 위치를 반환한다.
• O(n)
  • 모든 노드 순회하면서 equals() 메소드로 같은 데이터가 있는지 찾는다.

기존의 배열리스트의 단점을 해결했으나, 데이터 추가, 조회 자체에 O(1) 성능 하락이 있다.

정리

• 노드와 연결 개념이 숙지했다면 이 파트는 어렵지 않게 할 수 있을 것이다.
• 연결리스트의 데이터 추가는 필요한 메모리만 사용한다. 배열리스트에서 낭비되는 메모리를 해결할 수 있다.
  • 연결 유지에는 추가 메모리가 이용되므로 단점도 존재한다.