[자료구조][단일 연결 리스트] 코딩테스트, 정보처리기사를 위한 기초 5

 

 

 

 

[이전 글]

2024.01.25 - [코딩테스트] - [자료구조][스택] 코딩테스트, 정보처리기사를 위한 기초 4

[자료구조][스택] 코딩테스트, 정보처리기사를 위한 기초 4

---

 

• Linked List 란?
  • 데이터의 집합을 나타내는 지료구조로, 각 데이터 요소를 노드(Node)라고 칭한다.
  • 각 노드는 데이터 필드와 다음 노드를 가리키는 링크(포인터)로 구성
  • 배열과 달리 메모리에 연속적으로 배치되지 않으며, 동적으로 크기가 조절된다.

 

 

출처 : 나무위키

 

 

 

• 주요 특징과 용어
  • 노드(Node) : 데이터와 다음 노드를 가리키는 링크로 구성된 기본 단위
  • 헤드(Head) : 링크드 리스트의 첫 번째 노드
  • 테일(Tail) : 링크드 리스트의 마지막 노드 (일부 구현에서는 테일이 없는 경우도 있음)
  • 링크(Link) : 각 노드가 다음 노드를 가리키는 참조

 

• 링크드 리스트의 종류 
  • 단일 연결 리스트 (Singly Linked List) : 각 노드가 다음 노드를 가리키는 구조
    • 장점 : 구현이 간단하고 일반 배열의 단점(데이터 추가, 삭제)을 보완
    • 단점 : 첫 노드 부터 다음 노드 순으로 순차적으로 노드를 찾아야 하는 구조여서 마지막 노드를 찾을 경우 느림
  • 이중 연결 리스트 (Doubly Linked List) : 각 노드가 이전 노드와 다음 노드를 가리키는 구조
    • 장점 : 단일 연결 리스트의 단점을 보완하여 양방향으로 노드를 연결하여 리스트 앞, 뒤로 탐색이 모두 가능
  • 순환 연결 리스트 (Circular Linked List) : 마지막 노드가 첫 번째 노드를 가리키는 구조

 

• 단일 연결 리스트 예제
  • 철수는 쉬는 시간이 시작 하자 마자 매점에 갔다. 첫번째로 도착한 철수는 1번으로 간식을 산다. 
  • 그 뒤로 수미가 왔고 순서대로 임정, 정희, 지웅이 줄을 섰다. 
  • 영이는 뒤늦게 왔는데 임정 앞으로 세치기를 하고, 정희는 다른 일이 생겨 매점에서 나간다. 

 

package linkedlist;

public class SingleLinkedListTest {
    public class Node<T> {
        T data;
        linkedlist.Node<T> next = null;

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

    public static 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.print("[" + node.data + "]");
                while (node.next != null) {
                    node = node.next;
                    System.out.print("-[" + node.data + "]");
                }
                System.out.println();
            }
        }

        /**
         * 특정 노드 사이에 데이터 추가
         *
         * @param data       : 추가 할 노드
         * @param targetData : 특정 노드
         */
        public void addNodeInside(T data, T targetData) {
            Node<T> findNode = this.findNode(targetData);

            if (findNode == null)
                this.addNode(data); //찾고자 하는 노드가 없으면 마지막에 노드 추가
            else {
                //특정 노드가 있다면 임시 저장
                Node<T> nextNode = findNode.next;
                //특정 노드 다음에 새로운 노드 생성 후 연결
                findNode.next = new Node<T>(data);
                //임시 저장한 노드를 새로 추가한 노드 다음 노드로 변경
                findNode.next.next = nextNode;
            }
        }

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

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

    public static void main(String[] args) {
        SingleLinkedList<String> singleLinkedList = new SingleLinkedList<>();
        singleLinkedList.addNode("철수");
        singleLinkedList.addNode("수미");
        singleLinkedList.addNode("임정");
        singleLinkedList.addNode("정희");
        singleLinkedList.addNode("지웅");
        singleLinkedList.printAll();
        System.out.println("> 수미 다음으로 영이 추가");
        singleLinkedList.addNodeInside("영이", "수미");
        singleLinkedList.printAll();
        System.out.println("> 정희 이탈");
        singleLinkedList.removeNode("정희");
        singleLinkedList.printAll();
    }
}

/**
 * [결과 값]
 *
 * [철수]-[수미]-[임정]-[정희]-[지웅]
 * > 수미 다음으로 영이 추가
 * [철수]-[수미]-[영이]-[임정]-[정희]-[지웅]
 * > 정희 이탈
 * [철수]-[수미]-[영이]-[임정]-[지웅]
 *
 */

 

 

 

---

 

[다음 글]

2024.01.26 - [코딩테스트] - [자료구조][이중 연결 리스트] 코딩테스트, 정보처리기사를 위한 기초 6

[자료구조][이중 연결 리스트] 코딩테스트, 정보처리기사를 위한 기초 6