Linked List는 무엇인가?

[목차]

1. LinkedList란 무엇인가? 

2. LinkedList를 구현하려면 Node가 필요하다
    2.1 python Node구현하기
    2.2 java Node 구현하기

3. LinkedList를 소스로 구현해보자 
    3.1 python LinkedList 구현해보기 
    3.2 java LinkedList 구현해보기

4. BigO표기

1. LinkedList란 무엇인가? 

일단 LinkedList란 말 그대로 연결된 리스트라는 뜻이다. 그렇다면 리스트란 무엇인가? 리스트란 데이터를 연속적으로 저장하는 자료구조이다. 나무 위키에서 본 리스트의 정의는 아래와 같다. 

추상적 자료형, 자료구조의 하나. 순열(Sequence)이라고도 불리며, 순서를 가지고[1] 일렬로 나열한 원소들의 모임으로 정의한다. 순서가 있다는 점에서 집합과는 구별되며, 갈림길 없이 일렬로 나열되어
처음과 끝이 각각 하나씩만 있다는 점에서 그래프와도 구별된다.

그럼 나무위키에서 정의한 연결형 리스트는 무엇인가? 

추상적 자료형인 리스트를 구현한 자료구조로, Linked List라는 말 그대로 어떤 데이터 덩어리(이하 노드Node)를 저장할 때 그 다음 순서의 자료가 있는 위치를 데이터에 포함시키는 방식으로 자료를 저장한다.
예를 들어 한 반에 있는 학생들의 자료를 저장한다면, 학생 하나하나의 신상명세 자료를 노드로 만들고,
1번 학생의 신상명세 자료에 2번 학생 신상명세가 어디있는지 표시를 해 놓는 방식이다.
쉽게 생각하면 자료를 비엔나 소시지마냥 줄줄이 엮어놓은 것이다.

 

2. LinkedList를 구현하려면 Node가 필요하다

2.1 Python Node구현하기

class Node:
    def __init__(self, value=0, next=None):
        self.value = value
        self.next = next

2.2 Java Node 구현하기

package list.linkedlist;

public class Node {
    private int value;
    private Node next;

    public Node(int value, Node next) {
        this.value = value;
        this.next = next;
    }
}

그림을 그린다면 이렇게 표현할 수가 있다. value부분에 데이터를 입력하고 next부분에 다음 노드의 주소를 입력한다. 

3. LinkedList를 소스로 구현해보자 

3.1 python LinkedList 구현해보기. 

class LinkedList:
    def __init__(self):
        self.head = None

    def append(self, value):
        new_node = Node(value)
        if self.head is None:
            self.head = new_node
        else:
            current = self.head
            while current.next is not None:
                current = current.next
            current.next = new_node

    def display(self):
        current = self.head
        while current is not None:
            print(current.value)
            current = current.next

간단하게 append method만 구현을 해보았다. 아래처럼 실행을 해본다면 

test = LinkedList()
test.append(1)
test.append(2)
test.append(3)
test.append(4)

test.display()

이런식으로 결과값이 나온다. 이것을 그림으로 그려본다면 아래와 같다. 

 

3.2 java LinkedList 구현해보기

package org.example.datastructure.list;

import lombok.extern.slf4j.Slf4j;

class Node {
    private int value;
    private Node next;

    public Node(int value) {
        this(value, null);
    }

    public Node(int value, Node next) {
        this.value = value;
        this.next = next;
    }

    public int getValue() {
        return value;
    }

    public Node getNext() {
        return next;
    }

    public void setNext(Node next) {
        this.next = next;
    }
}

@Slf4j
public class LinkedList {
    private Node head;

    public void append(int value) {
        Node new_node = new Node(value);
        if (head == null) {
            head = new_node;
        } else {
            Node current = head;
            while (current.getNext() != null) {
                current = current.getNext();
            }
            current.setNext(new_node);
        }
    }

    public void display() {
        Node current = head;
        while (current != null) {
            log.info(String.valueOf(current.getValue()));
            current = current.getNext();
        }
    }
}

package org.example;

import lombok.extern.slf4j.Slf4j;
import org.example.datastructure.list.LinkedList;

@Slf4j
public class Main {

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

    }
}

연결리스트로 잘 연결되어있는것을 display method를 통해서 보았다. 

4. BigO표기

 

BigO표기가 ArrayList보다는 좋은 점은 ArrayList는 처음에 데이터를 입력하고자 하면 데이터를 입력후 오른쪽에 기존에 있는 데이터를 하나씩 미루어줘야하는데 LinkedList는 그렇게 하지 않아도 되니 좋은 점이다. 하지만 Singly linkedList는 중간에 입력하면 그 중간을 찾으려면 O(n)의 시간이 걸릴수 밖에 없다. 이것을 보완하는 방법은 Doubly LinkedList이다. 어려운건 아니고 head에다가 tail을 추가하는 것이다. 나중에 Doubly LinkedList에 대해서 더 보충하도록 하겠다.