[Data Structure] Linked List(연결 리스트)

1. Linked List 구조

인접하지 않은(떨어진) 곳에 존재하는 데이터를 포인터를 이용하여, 연결해 관리하는 데이터의 구조를 말함

Linked List

 

- 구조와 용어 -

Node(노드) : 데이터 저장 단위(데이터 값, 포인터)로 구성

Pointer(포인터) : 각 노드 안에서, 다음 혹은 이전의 노드와의 연결 정보를 가지고 있는 공간

 

- 장점 -

• 동적 배열이기에 런타임 시, 메모리의 할당 및 해제로 확장 및 축소가 가능하므로 데이터 공간을 미리 할당하지 않아도 됨
• 엘리먼트(Data) 삭제 후, 따로 이동할 필요없이 다음 포인터의 주소만 업데이트 시켜주면 되므로 관리에 용이함

- 단점 -

• 연결을 위한 별도의 데이터 공간이 필요하므로, 저장 공간의 효율이 낮아질 수 있음
• 해당 데이터를 찾으려면, 그 이전의 노드를 모두 순회해야 하는 시간이 필요하므로 접근 속도가 느림
• 중간 데이터 삭제 시, 앞 뒤 데이터의 연결을 재구성해야 하는 부가적인 작업 필요

 

2. Java 에서의 Linked List

java.util 패키지에서 제공

item 을 추가하는 기능으로 add(), addFirst(), addLast() 등의 메서드 제공

item 을 삭제하는 기능으로 remove(), removeFirst(), removeLast() 등의 메서드 제공

3. Example

public class SingleLinkedList<T> {
    public Node<T> head = null;

    public static class Node<T> {
        T data;
        Node<T> next =  null;

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

    public void addNode(T data) {
        if (this.head == null) {
            head = new Node<T>(data);
        } else {
            Node<T> node = this.head;
            while (node.next != null) {
                node = node.next;
            }
            node.next = new Node<T>(data);
        }
    }

    public Node<T> searchNode(T data) {
        if (this.head != null) {
            Node<T> node = this.head;
            while (node.data != null) {
                if (node.data == data) {
                    return node;
                } else {
                    node = node.next;
                }
            }
        }
        return null;
    }

    public void addNodeInside(T data, T isData) {
        Node<T> searchedNode = this.searchNode(isData);

        if (searchedNode == null) {
            this.addNode(data);
        } else {
            Node<T> nextNode = searchedNode.next;
            searchedNode.next = new Node<T>(data);
            searchedNode.next.next = nextNode;
        }
    }

    public boolean deleteNode(T isData) {
        if (this.head == null) {
            return false;
        } else {
            Node<T> node = this.head;
            if (node.data == isData) {
                this.head = this.head.next;
                return true;
            } else {
                while (node.next != null) {
                    if (node.next.data == isData) {
                        node.next = node.next.next;
                        return true;
                    }
                    node = node.next;
                }
                return false;
            }
        }
    }

    public void printAll() {
        if (head != null) {
            Node<T> node = this.head;
            System.out.println(node.data);
            while (node.next != null) {
                node = node.next;
                System.out.println(node.data);
            }
        }
    }

    public static void main(String[] args) {
        SingleLinkedList<Integer> linkedList = new SingleLinkedList<>();
        linkedList.addNode(1);
        linkedList.addNode(2);
        linkedList.addNode(3);
        linkedList.addNodeInside(4, 1);
        linkedList.deleteNode(2);
        linkedList.printAll();
    }
}

 

- 끝 -