[Fast Campus] 한 번에 끝내는 코딩테스트 369 : 링크드 리스트

✨ 링크드 리스트

링크드 리스트(Linked List) 구조

• 떨어진 곳에 존재하는 데이터를 화살표로 연결해서 관리하는 데이터 구조 (= 연결 리스트)
• 배열은 순차적으로 연결된 공간에 데이터를 나열하는 데이터 구조

링크드 리스트 기본 구조와 용어

• 노드(Node) : 데이터 저장 단위(데이터값, 포인터)로 구성
• 포인터(Pointer) : 각 노드 안에서, 다음이나 이전의 노드와의 연결 정보를 가지고 있는 공간
  

간단한 링크드 리스트 예

Node 클래스 구현

public class Node<T> {
    T data;
    Node<T> next = null;
    public Node(T data) {
        this.data = data;
    }
}

Node와 Node 연결하기 : Node 인스턴스간 연결

Node<Integer> node1 = new Node<Integer>(1);
Node<Integer> node2 = new Node<Integer>(2);
node1.next = node2;
Node<Integer> head = node1;

링크드 리스트에 데이터 추가하기

public class SingleLinkedList<T> {
    public Node<T> head = null;
    public class Node<T> {
        T data;
        Node<T> next = null;
        public Node(T data) {
            this.data = data;
        }
    }
    public void addNode(T data) {
        if (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 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);
        }
    }
}

링크드 리스트의 장단점

• 장점
  • 미리 데이터 공간을 할당하지 않아도 됨 (배열은 미리 공간 할당 필요)
• 단점
  • 연결을 위한 별도 데이터 공간이 필요하므로, 저장공간 효율이 높지 않음
  • 연결 정보를 찾는 시간이 필요하므로 접근 속도가 느림
  • 중간 데이터 삭제시, 앞뒤 데이터의 연결을 재구성해야하는 부가적인 작업 필요

링크드 리스트의 복잡한 기능 1 (데이터 사이에 데이터를 추가)

• 링크드 리스트는 유지 관리에 부가적인 구현이 필요
  

public class SingleLinkedList<T> {
    public Node<T> head = null;    
    public class Node<T> {
        T data;
        Node<T> next = null;        
        public Node(T data) {
            this.data = data;
        }
    }   
    public void addNode(T data) {
        if (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 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 Node<T> search(T data) {
        if (this.head == null) {
            return null;
        } else {
            Node<T> node = this.head;
            while(node != null) {
                if (node.data == data) {
                    return node;
                } else {
                    node = node.next;
                }
            }
            return null;
        }
    }
    public void addNodeInside(T data, T isData) {
        Node<T> searchedNode = this.search(isData);
        if (searchedNode == null) {
            this.addNode(data);
        } else {
            Node<T> nextNode = searchedNode.next;
            searchedNode.next = new Node<T>(data);
            searchedNode.next.next = nextNode;
        }
    }
}

링크드 리스트의 복잡한 기능 2 (특정 노드를 삭제)

public boolean delNode(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;
        }
    }
}

✨ 다양한 링크드 리스트

더블 링크드 리스트 (Doubly linked list)

• 이중 연결리스트라고도 함
• 양방향으로 연결되어 있어서 노드 탐색이 양쪽으로 모두 가능
  

public class DoubleLinkedList<T> {
    public Node<T> head = null;
    public Node<T> tail = null;    
    public class Node<T> {
        T data;
        Node<T> prev = null;
        Node<T> next = null;
        public Node(T data) {
            this.data = data;
        }
    }
    public void addNode(T data) {
        if (this.head == null) {
            this.head = new Node<T>(data);
            this.tail = this.head;
        } else {
            Node<T> node = this.head;
            while (node.next != null) {
                node = node.next;
            }
            node.next = new Node<T>(data);
            node.next.prev = node;
            this.tail = node.next;
        }
    } 
    public void printAll() {
        if (this.head != null) {
            Node<T> node = this.head;
            System.out.println(node.data);
            while (node.next != null) {
                node = node.next;
                System.out.println(node.data);
            }
        }
    }
}

Search 함수 추가하기 (head, tail)

public T searchFromHead(T isData) {
    if (this.head == null) {
        return null;
    } else {
        Node<T> node = this.head;
        while (node != null) {
            if (node.data == isData) {
                return node.data;
            } else {
                node = node.next;
            }
        }
        return null;
    }     
}    
public T searchFromTail(T isData) {
    if (this.head == null) {
        return null;
    } else {
        Node<T> node = this.tail;
        while (node != null) {
            if (node.data == isData) {
                return node.data;
            } else {
                node = node.prev;
            }
        }
        return null;
    }
}

임의의 노드 앞에 추가하기

    public boolean insertToFront(T existedData, T addData) {
        if (this.head == null) {
            this.head = new Node<T>(addData);
            this.tail = this.head;
            return true;
        } else if (this.head.data == existedData) {
            Node<T> newHead = new Node<T>(addData);
            newHead.next = this.head;
            this.head = newHead;
            this.head.next.prev = this.head;          
            return true;
        } else {
            Node<T> node = this.head;
            while (node != null) {
                if (node.data == existedData) {
                    Node<T> nodePrev = node.prev;
                    nodePrev.next = new Node<T>(addData);
                    nodePrev.next.next = node;
                    nodePrev.next.prev = nodePrev;
                    node.prev = nodePrev.next;
                    return true;
                } else {
                    node = node.next;
                }
            }
            return false;
        }
    }

---

📝 마치며

2학년때 자료구조를 수강하면서 링크드 리스트가 조금 어렵다는 느낌이 있었는데, 그 부분을 보충할 수 있어서 좋았다. 아주 많이 사용하는 자료구조이기 때문에 숙달이 필요할 것 같다.