글 쓰는 시간

연결 리스트 

연결 리스트는 내부에 노드 와 헤더를 갖는다.

노드는 데이터를 갖고 다음 노드의 주소값을 알고있다.

자바로 단방향 연결 리스트 구현

자바로 단방향 연결 리스트를 구현해보았다. 자료구조의 개념을 익히기 위함이라 완벽한 구현은 아닐수도 있다.

간단하게 내부 클래스로 Node 를 만들고 연결 리스트의 추가, 삭제, 조회 메서드를 구현했다.

첫 생성 시엔  다음 노드의 주소값의 초기값을 null 로 줘서 다음 주소값을 모르도록 설정했다.

연결 리스트를 생성하는 시점에 첫 노드로서 헤더를 만들고 생성, 삭제, 조회 시 헤더가 이 메서드들의 반복문의 시작점이 된다.

조회 시 헤더를 조회 할 필요는 없으므로 헤더의 다음 노드부터 조회한다.

public class LinkedList {
    Nodes header;

    public LinkedList() {
        header = new Node();
    }

    // 추가
    void append(int d) {
        Node end = new Node(d);
        Node n = header;
        while (n.next != null) {
            n = n.next;
        }
        n.next = end;
    }

    // 삭제
    void delete(int data) {
        Node n = header;
        while (n.next != null) {
            if (n.next.data == data) {
                n.next = n.next.next;
            } else {
                n = n.next;
            }
        }
    }

    // 조회
    void retrieve() {
        Node n = header.next;
        while (n.next != null) {
            System.out.print(n.data + " -> ");
            n = n.next;
        }
        System.out.println(n.data);
    }

    public static class Node {
        int data;
        Node next = null;

        public Node() {
        }

        public Node(int data) {
            this.data = data;
        }
    }
}

ㄴ append()

데이터 값을 매개변수로 받아 그 데이터로 마지막 노드를 만들고

처음부터 반복문을 돌아서 이전 마지막 노드를 찾아 그 노드에 새로 만든 마지막 노드의 주소값을 할당한다.

ㄴ delete()

데이터 값을 매개변수로 받아 반복문을 돌아 그 데이터에 해당하는 목표 노드를 찾는다.

a -> b -> c 순서의 노드 중 b 가 목표 노드라면 a 노드 에는 c 노드 주소를 할당한다.

ㄴ retrieve()

조회 시에는 header 의 데이터값을 조회 할 필요는 없으므로 header 의 다음 노드부터 시작해서

다음 노드 주소가 null 인 노드(마지막 노드) 까지 값을 출력한다.

LinkedList 클래스에 아래처럼 메인 메서드를 작성하면 제대로 동작함을 알 수 있다.

public static void main(String[] args) {
    LinkedList linkedList = new LinkedList();
    linkedList.append(1);
    linkedList.append(2);
    linkedList.append(3);
    linkedList.append(4);
    linkedList.append(5);
    linkedList.retrieve();
    linkedList.delete(1);
    linkedList.delete(4);
    linkedList.retrieve();
}

LinkedList(연결 리스트) 란

컴퓨터에 자료를 저장하는 자료구조의 한 종류이다.

길이가 정해져있지 않으며 데이터를 저장한 노드에서 이전 노드가 다음 노드의 주소를 가지고있는 구조이다.

배열과의 비교 

1. 배열

배열방들이 물리적으로 연결돼있어서 크기를 정하면 늘이거나 줄일수없다.

2. 연결 리스트

노드가 갖고 있는 주소를 변경하면 늘이거나 줄일 수 있다.

하지만 메모리는 여전히 갖고있기 때문에 자바같이 사용하지 않는 메모리를 알아서 정리해주 언어가 아니면

안쓰겠다고 명시해줘야 다른 애들이 그 메모리를 쓸수있다.

연결 리스트는 조회 시 배열보다 속도는 느리지만 배열은 크기 변경 시 변경사항을 적용한

배열을 통째로 다시 값을 할당해줘야하므로 길이가 정해지지 않은 데이터 핸들링엔 연결 리스트가 좋다.

연결 리스트 단/양방향

내 다음 노드 주소만 알고있어서 조회 시 앞에있는 노드애부터 하나씩 조회해야하면 단방향이다.

내 다음 노드와 이전 노드의 주소도 알고 있어서 양쪽으로 조회 가능하면 양방향이다.

양방향은 내 다음 노드와 이전 노드의 주소값 모두 알아야하므로 단방향보다는 메모리를 많이 먹는다.

따라서 양방향 조회가 필요 없으면 단방향으로 하고 필요하면 양방향으로 유연하게 선택하자.