🍠Linked list

Linked list (연결 리스트)란?

연결 리스트, 링크드 리스트(linked list)는 각 노드가 데이터와 포인터를 가지고 한 줄로 연결되어 있는 방식으로 데이터를 저장하는 자료 구조이다. 이름에서 말하듯이 데이터를 담고 있는 노드들이 연결되어 있는데, 노드의 포인터가 다음이나 이전의 노드와의 연결을 담당하게 된다.

• 고구마 줄기

  → 고구마 줄기라고 생각해보기. 처음 시작 부분만 알고있다, 그 시작 부분을 타고 들어가다 보면 고구마(data)가 계속 줄줄이 나온다. 시작(주소) - 연결(link) - 끝(null pointer or circular)

  위의 순서가 존재함을 기억하기.

구조

노드(Node)와 링크(Link)로 구성되며, 노드는 실제 정보를 담고 있는 하나의 단위이고, 링크는 노드간의 위치정보를 저장하고 있어 연결리스트의 순서를 유지할 수 있도록 하는 연결고리라 할 수 있다.

노드의 시작점은 head, 끝점은 tail이라 부르며 노드의 추가, 삭제, 탐색이 가능하다.

배열 리스트와 연결 리스트의 장단점

1. 배열리스트

   • 가장 간단한 메모리 데이터 구조

   장점

   • 동일한 데이터 타입을 연속적으로 저장할 수 있다.
   • 간단하고, 사용이 쉬우며 데이터를 참조하기 쉽다.

   단점

   • 고정된 크기(JS 제외)를 가지고 있어서 배열의 처음이나 중간에서 원소를 넣고 빼려면 비싼 연산을 빈번하게 해야 한다.

2. 연결 리스트

   • 일련의 원소를 배열처럼 차례대로 저장하지만 원소들이 메모리상에 연속적으로 위치하지 않는다. 노드로 구현된 리스트이다. 링크 하나에 4 byte 메모리를 차지하며, 더블 링크드일 경우엔 노드 하나에 8 byte의 링크 메모리를 차지한다.

탐색과 정렬을 자주 한다면 배열 리스트
추가와 삭제가 많다면 연결 리스트

Linked list (연결 리스트) 특징

1. 연속되는 항목들이 포인트로 연결되어 있다.

2. 마지막 항목은 Null을 가리키고 있음. (마지막이라 연결한 노드가 없기 때문)

3. 프로그램이 수행되는 동안 크기가 동적으로 커지거나 작아짐.

4. 메모리 공간 낭비가 적지만 포인터 메모리가 필요함.

5. 배열에 비해 데이터의 추가와 삽입에 용이.

6. 단방향(양방향이라도) 순차적으로 탐색하지 않으면 요소에 접근이 불가하기 때문에 탐색 속도가 떨어짐.

7. 데이터를 추가하는 건 객체 할당임.

8. 링크를 끊어 버리면 데이터가 삭제되기 때문에 (JS기준) 만약 head에서 노드를 전체 삭제하고 싶다면 head에 있는 링크를 끊어 버리기만 하면 된다.

   

위의 이미지를 코드로 본다면.

head: {0: 'apple', next: {1: 'banana', next: {2: 'dream', next: null}}}}
tail: {2: 'dream', next: null}

만약 삭제하고싶다면?

data2를 삭제해 주는 것이 아니라, data1의 링크를 2가 아닌 3으로 다시 연결을 해주면 data2는 head에서 자동으로 빠지게되어 없어진다. 추가도 마찬가지이다. 1과 3 사이에 데이터를 넣게 된다면 1의 링크를 3이아닌 넣으려는 데이터에 연결하고, 넣으려는 데이터를 3으로 연결해주면된다.

연결 리스트의 종류

1. Singly linked list (일방향 연결 리스트)
   지금까지 위의 설명들이 바로 일방향 연결 리스트이다. 일방향 연결 리스트는 노드에 포인터(다음 노드를 가리키는 링크)가 한 개인 연결 리스트인데, 이 리스트의 장점은 노드당 포인터 데이터를 4바이트만 차지해서 이중 연결 리스트보다 데이터를 아낄 수 있다는 점이다. 다만 일방향이기 때문에 현재 노드는 이전 노드로 돌아가는 법을 모른다. 오직 직진만이 있을 뿐.

2. Doubly linked list (이중 연결 리스트)

   노드에 포인터가 두 개 있는 이중 연결 리스트인데, 일방향 연결 리스트와 똑같지만 앞서 말한 것처럼 노드에 포인터가 두 개 있다는 점이 다르다 이 두 개의 포인터는 전과 후를 가리키고 있기 때문에 일방향과는 달리 이전으로 갈 수도, 이후로도 갈 수도 있다. 포인터가 두 개가 생겼으니 데이터도 두 배로 먹는다. 8바이트를 차지합니다.

3. Circular linked list (환형 연결 리스트)

   연결 리스트에 있는 헤드와 테일이 붙여져 있어, 원의 모양과 같다고 하여 환형 리스트이다. 테일의 포인터가 null을 가리키고 있는 것이 아닌 head를 가리키고 있는 것인데, 노드 6 번에 있다가 4 번으로 가야 된다면, 일방향 리스트는 다시 시작해야 되지만 환형 리스트는 7, 8, 9, 10을 지나 다시 0, 1, 2, 3, 4로 갈 수 있다 즉 순회할 때 좋은 연결 리스트이다.

LinkedList - Java 구현 - Data Structure (자료구조)

//코드는 egoing님 강의 참초하며 실습했습니다.
package com.hajni.lib;

import java.nio.channels.FileLockInterruptionException;
import java.util.ListIterator;

public class LinkedList {
    private Node head;  //  누가 첫번째인가.
    private Node tail;  //  제일 끝에 있는가.
    private int size = 0;

    private class Node {
        private Object data;    // 데이터가 저장될 필드
        private Node nexe;      // 다음 노드를 가리키는 필드.

        public Node(Object input) {  // Node가 생성되어있을때 가지고 있는 값이 input의 매개변수로 전달
            this.data = input;
            this.nexe = null;
        }

        public String toString() {   // 노드의 내용을 출력해서 확인할 수 있는 기능
            return String.valueOf(this.data);
        }
    }

    // 처음에 추가
    public void addFirst(Object input) {
        Node newNode = new Node(input);
        newNode.nexe = head;    // 새로운 노드의 다음 노드를 head지정
        head = newNode;         // head로 새로운 노드를 지정
        size++;

        if (head.nexe == null) {
            tail = head;
        }
    }

    // 끝에 추가
    public void addLast(Object input) {
        Node newNode = new Node(input);
        if (size == 0) {
            addFirst(input);
        } else {
            /**
             * 마지막 노드(tail)의 다음 노드(next)가 새 노드를 가리키도록 하고
             * tail이 가리키는 노드를 새 노드로 바꿔준다.
             */
            tail.nexe = newNode;
            tail = newNode;
            size++;
        }

    }

    // 노드 추가하기 전 특정 위치 노드 찾아냄
    Node node(int index) {
        Node x = head;
//        x = x.nexe;  -> 만약 index100번째를 가져오려면 x 100 을해야한다 = 반복문사용해야함.
        for (int i = 0; i < index; i++) {
            x = x.nexe;
        }
        return x;
    }

    // 특정위치 노드 추가 메소드
    public void add(int k, Object input) {
        if (k == 0) {
            addFirst(input);
        } else {
            Node temp1 = node(k - 1);
            Node temp2 = temp1.nexe;
            Node newNode = new Node(input);

            /**
             * 이전 노드가 가리키는 노드를 끊은 뒤
             * 새 노드로 변경해준다.
             * 또한 새 노드가 가리키는 노드는 temp2로
             * 설정해준다.
             */
            temp1.nexe = newNode;
            newNode.nexe = temp2;
            size++;
            if (newNode.nexe == null){
                tail = newNode;
            }
        }
    }

    // 리스트 확인 코드
    public String toString(){
        if (head == null){
            return "[]";
        }

        Node temp = head;
        String str = "[";

        while(temp.nexe != null){
            str += temp.data + " , ";
            temp = temp.nexe;
        }
        str += temp.data;
        return str + "]";

    }

    // 첫번째 노드 삭제
    public Object removeFirst(){
        Node temp = head;
        head = head.nexe;
        Object returnData = temp.data;  // 데이터 삭제 전 리턴할 값을 임시 변수에 담는다.
        temp = null;
        size--;
        return returnData;
    }

    // 중간 노드 삭제
    public Object remove(int k){
        if (k == 0){
            return removeFirst();
        }
        Node temp = node(k - 1);  // 삭제할 노드의 이전 노드
        Node todoDeleted = temp.nexe;   // 삭제할 노드
        temp.nexe = temp.nexe.nexe;     // 삭제할 노드의 다음 노드
        Object returnData = todoDeleted.data;   // 삭제되는 노드의 데이터를 반환하기 위한 임시변수

        if (todoDeleted == tail){
            tail = temp;
        }
        todoDeleted = null;
        size--;

        return returnData;
    }

    public Object removeLast(){
        return remove(size - 1);    //
    }

    public int size(){
        return size;
    }

    public Object get(int k){
        Node temp = node(k);
        return temp.data;
    }

    public Object indexOf(Object data){
        Node temp = head;
        int index = 0;
        while (temp.data != data){
            temp = temp.nexe;
            index++;

            if (temp == null){
                return -1; // 찾고자 하는 요소를 찾지 못했을 경우 -1 반환
            }
        }
        return index;
    }

    public ListIterator listIterator() {
        return new ListIterator();
    }
    class ListIterator{
        private Node lastReturned;
        private Node next;
        private int nextIndex;

        ListIterator(){
            next = head;
            nextIndex = 0;
        }

        public Object next(){
            lastReturned = next;
            next = next.nexe;
            nextIndex++;

            return lastReturned.data;
        }

        public boolean hasNext(){
            return nextIndex < size();
        }

        public void add(Object input){
            Node newNode = new Node(input);

            if (lastReturned == null){
                // 처음위치에 노드를 추가하는 ㅋ드
                head = newNode;
                newNode.nexe = next;
            }else {
                // 중간에 추가하는 코드
                lastReturned.nexe = newNode;
                newNode.nexe = next;
            }

            lastReturned = newNode;
            nextIndex++;
            size++;
        }

        public void remove(){
             if (nextIndex == 0){
                 throw new IllegalStateException();
             }
             LinkedList.this.remove(nextIndex - 1);
             nextIndex--;
        }
    }

}