본문 바로가기
개발/자료구조

[자료구조] 링크드리스트(LinkedList)

by 난중후니 2023. 1. 19.
728x90
반응형

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

  • 연결 리스트라고도 합니다.
  • Linked List는 떨어진 곳에 존재하는 데이터를 주소로 연결하여 관리하는 데이터 구조입니다.

LinkedList 기본 구조와 용어

  • 노드(Node): 데이터 저장 단위(데이터값, 포인터)로 구성됩니다.
  • 포인터(pointer): 각 노드 안에서 다음이나 이전의 노드와의 연결 정보(주소)를 가지고 있는 공간입니다.
  • 일반적인 LinkedList 형태

null

null

null

[출처 - 위키피디아 백과사전]

2. LinkedList 예시

Node 클래스 구현

public clfgass 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 head = node1;

LinkedList 데이터 추가

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);
            }
        }
    }
}

LinkedList 데이터 출력(조회)

3. LinkedList 장단점

장점

  • 이전, 다음 데이터 값에 대한 주소를 포함하고 있으므로 연속된 데이터 공간이 필요가 없습니다. 따라서 데이터 공간을 미리 할당하지 않아도 됩니다.

단점

  • 데이터 값에 대한 주소를 갖기 위한 데이터 공간이 필요하므로 저장공간 효율이 높지 않습니다.
  • 연결 정보를 찾는 시간이 필요하므로 접근 속도가 느립니다(LinkedList는 항상 맨 앞의 데이터부터 찾아서 다음 주소값을 찾는 작업이 필요하기 때문입니다)
  • 중간 데이터가 삭제되는 경우 앞 뒤 데이터의 연결을 재구성해야 하는 부가적인 작업이 필요합니다.

4. LinkedList 데이터 사이에 데이터를 추가, 삭제

  • LinkedList는 유지 관리에 부가적인 구현이 필요합니다.
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){ // data는 현재 Node의 data, isData는 현재 Node가 저장할 위치의 이전 data
        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;

        }
    }

    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;
            }
        }
    }

}
  • Node 추가
SingleLinkedList<Integer> linkedList = new SingleLinkedList<Integer>();


linkedList.addNode(1);  
linkedList.addNode(2);  
linkedList.addNode(3);

linkedList.printAll();  
System.out.println("===");

linkedList.addNodeInside(5, 1);  
linkedList.printAll();  
System.out.println("===");

linkedList.addNodeInside(7, 20);  
linkedList.printAll();

결과
1
2
3
===
1
5
2
3

===
1
5
2
3
7

  • Node 삭제

SingleLinkedList linkedList = new SingleLinkedList();

linkedList.addNode(1);
linkedList.addNode(2);
linkedList.addNode(3);

linkedList.printAll();
System.out.println("===");

System.out.println(delNode(3));
System.out.println(delNode(3));


결과
1
2
3
===
true
false

5. 다양한 링크드 리스트 구조: 더블 링크드 리스트(Doubly linked list)

  • 더블링크드 리스트(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);
            }
        }
    }

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

    public T searchFromTail(T data){
        if(this.tail == null){
            return null;
        }else{
            Node<T> node = this.tail;
            while (node != null){
                if(node.data == data){
                    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;
            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;
        }
    }
}
DoubleLinkedList<Integer> doubleLinkedList = new DoubleLinkedList<Integer>();
doubleLinkedList.addNode(2);
doubleLinkedList.addNode(4);
doubleLinkedList.addNode(8);
doubleLinkedList.addNode(16);
doubleLinkedList.addNode(32);

doubleLinekdList.printlnAll();
System.out.println(doubleLinekdList.searchFromHead(8));
System.out.println(doubleLinekdList.searchFromTail(32));
System.out.println(doubleLinekdList.insertToFront(3, 5));
System.out.println(doubleLinekdList.insertToFront(2, 1));

/**
결과
2
4
8
16
32
8
32
false
true
**/
728x90
반응형
저작자표시

'개발 > 자료구조' 카테고리의 다른 글

[자료구조] 트리(Tree)  (0) 2023.01.29
[자료구조] 큐(Queue)란?  (0) 2022.12.29
[자료구조] 스택(Stack) 이란?  (0) 2022.12.29
[자료구조] 배열과 해시테이블의 차이점  (0) 2022.12.29
[자료구조] 해시테이블이란?  (0) 2022.12.29

관련글

댓글

티스토리툴바