자료구조

Linked List (연결리스트)

데이터를 담고있는 단위인 Node가 연결되어 List처럼 구성된 자료구조

Node

연결 리스트의 데이터를 담고있는 단위로 하나의 노드는 아래의 값을 가지고 있다.

• 하나의 데이터
• 다음 Node

종류

• 단일 연결 리스트
  

• 이중 연결 리스트
  

• 원형 연결 리스트(단방향)
  

장,단점

• 동적 크기 조정

  크기를 미리 정의해야 하는 배열과 달리 리스트는 런타임때 필요에 따라 크기조정이 가능함.

• 삽입, 삭제 효율성

  중간에서의 삽입, 삭제가 효율적임.

  배열은 해당 인덱스 전후의 모든 데이터를 이동시켜야 하지만, 리스트는 직전, 직후 노드의 포인터만 바꿔주면 되므로 비용이 낮음.

• 메모리 효율

  배열처럼 메모리를 연속적으로 할당할 필요가 없어 메모리 단편화(Memory Fragmentation) 문제를 피할 수 있음.

---

단일 연결 리스트

하나의 노드가 다음 노드의 정보만을 가지고 있는 리스트

단일 연결 리스트 메소드

• push

  코드

  public void push(Integer data){
          Node node = new Node(data);
          // 리스트가 비었을때
          if (this.length == 0){
              head = node;
              tail = node;
              length++;
          } else { //나머지
              tail.setNext(node);
              tail = node;
              length++;
          }
  
      }

• delete
  

  코드

       public void delete(){
          Node node = new Node();
          node = head;
  
          //리스트가 비었을 때
          if (length == 0){
              System.out.println("리스트가 비었습니다.");
              return;
          } else if (length == 1) { //노드가 1개일 때
              head = null;
              tail = null;
              length--;
          }else { //나머지
              for (int i = 0; i < this.length; i++) {
                  if (i == this.length-2){
                      node.setNext(null);
                      tail = node;
                      length--;
                      return;
                  }
                  node = node.getNext();
              }
          }
      }

• shift

  코드

        public void shift(){
          //리스트가 비었을 때
          if (length == 0){
              System.out.println("리스트가 비었습니다.");
              return;
          }else if(length == 1){ //노드가 1개일 때
              head = null;
              tail = null;
              length--;
          }else { //나머지
              head = head.getNext();
              length--;
          }
      }

• unshift

  코드

  public void unShift(Integer data){
          Node node = new Node(data);
          node.setNext(head);
          head = node;
          length++;
      }

• isEmpty

  코드

     public Boolean isEmpty(){
          return (length==0 ? true : false);
      }

• insert

  코드

  public void insert(Integer order, Integer data){
          Node node = new Node(data);
          Node prevNode = head;
          //length+1보다 크거나 1보다 작을때
          if (order > this.length+1 || order < 1){
              System.out.println("추가할 수 없는 위치입니다.");
              return;
          } else if (order == 1) {//head일때
              node.setNext(head);
              head = node;
              length++;
          } else if (order == length+1) {//tail일 때
              tail.setNext(node);
              tail = node;
              length++;
          }else {//나머지
              for (int i = 0; i < order; i++) {
                  if (i == order-2){
                      node.setNext(prevNode.getNext());
                      prevNode.setNext(node);
                      length++;
                      return;
                  }
                  prevNode = prevNode.getNext();
              }
          }
  
      }

• deleteAt

  코드

    public void deleteAt(Integer order){
          Node n = head;
          //현재 길이보다 큰 값일 때
          if(order > length){
              System.out.println("리스트의 길이보다 큽니다.");
              return;
          }else if (order == 1){ //head일 때
              head = head.getNext();
              length--;
          } else if (order == length) {//tail일 때
              for (int i = 0; i < this.length; i++) {
                  if (n.getNext() == tail){
                      n.setNext(null);
                      tail = n;
                      length--;
                      return;
                  }
                  n = n.getNext();
              }
          }else { //나머지
              for (int i = 0; i < order; i++) {
                  if (i == order-2){
                      n.setNext(n.getNext().getNext());
                      length--;
                      return;
                  }
                  n = n.getNext();
              }
          }
  
      }

• printList

  코드

      public void printList(){
            Node node = new Node();
            node = head;
            System.out.println("Linked List 전체 출력");
            for (int i = 0; i < this.length; i++) {
                System.out.println(node.getData());
                node = node.getNext();
            }
        }

---

이중 연결 리스트

하나의 노드가 여러 노드의 정보를 가지고 있는 리스트

특징

• 이전과 다음 노드의 정보를 양방향으로 가지고 있다.
  
  
• 기존 단방향과 다르게 head, tail 양끝에서 탐색시작이 가능하다.

장점

• 양방향 탐색: 리스트 양끝에서 탐색 가능
  
  
• 삽입, 삭제 효율성: 기존 연결 리스트와 동일
  
  
• 끝단에서의 작업 효율: head부터 출발했던 단일 연결 리스트와 다르게, tail에서도 접근 가능하기 때문에 뒤쪽에서의 작업이 효율적

단점

• 더 많은 메모리 사용: 각 노드가 가지는 값이 많아졌기 때문에 단일 연결 리스트보다 메모리 사용량이 많음
  
  
• 구현 복잡성: 관리할 노드정보(포인터)가 많아지기 때문에 구현이나 유지보수가 더 복잡함

이중 연결 리스트 메소드

• append

  코드

      public void append(Integer data){
          DoubleNode node = new DoubleNode(data);
  
          if (tail == null){
              head = node;
              tail = node;
              length++;
          }else {
              tail.setNext(node);
              node.setPrev(tail);
              tail = node;
              length++;
          }
      } 

• prepend

  코드

    public void prepend(Integer data){
          DoubleNode node = new DoubleNode(data);
          if (length == 0){
              head = node;
              tail = node;
              length++;
          }else {
              node.setNext(head);
              head.setPrev(node);
              head = node;
              length++;
          }
  
      }

• insertAtPosition

  코드

    public void insertAtPosition(Integer position, Integer data){
          DoubleNode node = new DoubleNode(data);
          DoubleNode now = new DoubleNode();
  
          if (position > length+1 || position < 1){
              System.out.println("잘못된 입력");
          } else if (position == 1) {
              prepend(data);
          } else if (position == length){
              append(data);
          }else if (position > length/2){
              now = tail;
              for (int i = 0; i <= length-position; i++) {
                  if (i == (length-position)){
                      node.setNext(now);
                      node.setPrev(now.getPrev());
                      now.getPrev().setNext(node);
                      now.setPrev(node);
                      length++;
                      break;
                  }
                  now = now.getPrev();
              }
          }else {
              now = head;
              for (int i = 0; i < position; i++) {
                  if (i == position-2){
                      node.setNext(now.getNext());
                      node.setPrev(now);
                      now.setNext(node);
                      now.getNext().setPrev(node);
                      length++;
                      break;
                  }
                  now = now.getNext();
              }
          }
  
      }

• deleteFirst

  코드

        public void deleteFirst(){
          if (length == 0){
              System.out.println("리스트가 비었음");
          }else if (length == 1){
              head = null;
              tail = null;
              length--;
          }else {
              head = head.getNext();
              head.getPrev().setNext(null);
              head.setPrev(null);
              length--;
          }
      }

• deleteLast

  코드

        public void deleteLast(){
          if (length == 0){
              System.out.println("리스트가 비었음");
          } else if (length == 1) {
              head = null;
              tail = null;
              length --;
          }else {
              tail = tail.getPrev();
              tail.getNext().setPrev(null);
              tail.setNext(null);
              length--;
          }
      }

• deleteAtPosition

  코드

        public void deleteAtPosition(Integer position){
          DoubleNode now = new DoubleNode();
          if (position > length + 1 || position < 1){
              System.out.println("잘못된 입력");
          } else if (position == 1) {
              deleteFirst();
          } else if (position == length) {
              deleteLast();
          } else if (position > length/2) {
              now = tail;
              for (int i = 0; i <= length-position; i++) {
                  if (i == length-position){
                      now.getNext().setPrev(now.getPrev());
                      now.getPrev().setNext(now.getNext());
                      now.setNext(null);
                      now.setPrev(null);
                      length--;
                  }
                  now = now.getPrev();
              }
          }else {
              now = head;
              for (int i = 0; i < position; i++) {
                  if (i == position-1){
                      now.getNext().setPrev(now.getPrev());
                      now.getPrev().setNext(now.getNext());
                      now.setNext(null);
                      now.setPrev(null);
                      length--;
                  }
                  now = now.getNext();
              }
          }
  
      }

• isEmpty

  코드

        public Boolean isEmpty(){
          return (length == 0 ? true : false);
      }

• printList

  코드

        public void printList(){
          DoubleNode node = new DoubleNode();
          node = head;
          System.out.println("리스트 출력");
  
          for (int i = 0; i < length; i++) {
              if (length == 0){
                  System.out.println("빈리스트");
              }else {
                  System.out.println(node.getData());
  
              }
              node = node.getNext();
          }
      }

---

원형 연결 리스트

마지막 노드가 첫 번째 노드를 다시 가리키도록 연결된 리스트

특징

• 순환구조: 마지막 노드의 next가 첫 번째 노드를 가리킴
  
  
• 시작점이 없음: 시작점이 따로 없기 때문에 어떤 노드에서 시작해도 전체 리스트를 순회할 수 있음
  
  
• 종료 조건: 탐색이나 반복시 종료조건을 명확하게 설정해야 함

장점

• 순환의 효율성: 리스트의 모든 노드를 순환하는 작업이 효율적임. (current = current.getNext()로 복잡한 조건 없이 전체 리스트를 계속해서 순회할 수 있음)
  
  
• 끝과 시작 구분이 없음: 리스트의 끝과 시작으로 쉽게 이동할 수 있음

단점

• 무한루프 가능성: 순환구조이기 때문에 종료조건을 잘못 설정할 시 무한루프에 빠질 수 있음
  
  
• 복잡성: 기존 리스트에 순환구조가 추가되었기 때문에 유지보수와 구현이 조금 더 복잡함

활용

• 큐 구현
  
  
• 라운드 로빈 스케줄링
  
  
• 데이터 버퍼

원형 연결 리스트 메소드(단일 연결)

• append

  코드

      public void append(Integer data){
          Node node = new Node(data);
          if (length==0){
              head = node;
              tail = node;
              node.setNext(node);
              length++;
          }else {
              tail.setNext(node);
              node.setNext(head);
              tail = node;
              length++;
          }
      }

• prepend

  코드

      public void prepend(Integer data){
          Node node = new Node(data);
          if (length == 0){
              append(data);
          }else {
              node.setNext(head);
              head = node;
              tail.setNext(node);
              length++;
          }
      }

• insertAtPosition

  코드

      public void insertAtPosition(Integer position,Integer data){
          Node node = new Node(data);
          Node now = new Node();
          if (position < 1 || position > length+1){
              System.out.println("잘못된 위치");
          } else if (position == 1) {
              prepend(data);
          } else if(position == length){
              append(data);
          } else {
              now = head;
              for (int i = 0; i < position; i++) {
                  if (i == position-2){
                      node.setNext(now.getNext());
                      now.setNext(node);
                      length++;
                  }
                  now = now.getNext();
              }
  
          }
      }

• deleteFirst

  코드

      public void deleteFirst(){
          if (length == 0){
              System.out.println("빈 리스트");
          } else if (length == 1) {
              head = null;
              tail = null;
              length--;
          }else {
              head = head.getNext();
              tail.getNext().setNext(null);
              tail.setNext(head);
              length--;
          }
      }

• deleteLast

  코드

      public void deleteLast(){
          Node now = new Node();
          now = head;
          if (length == 0 || length == 1){
              deleteFirst();
          }else {
              for (int i = 0; i < length; i++) {
                  if (now.getNext() == tail){
                      now.setNext(head);
                      tail.setNext(null);
                      tail = now;
                      length--;
                      break;
                  }
                  now = now.getNext();
              }
          }
      }

• deleteAtPosition

  코드

      public void deleteAtPosition(Integer position, Integer data){
          Node now = new Node();
          if (position < 1 || position > length +1){
              System.out.println("잘못된 위치");
          } else if (position == 1) {
              deleteFirst();
          } else if (position == length) {
              deleteLast();
          }else {
              now = head;
              for (int i = 0; i < position; i++) {
                  if (i == position-2){
  
                  }
              }
          }
  
      }

• isEmpty

  코드

        public Boolean isEmpty(){
          return (length == 0 ? true : false);
      }

• printList

  코드

  
      public void printList(){
          Node now = new Node();
          now = head;
          System.out.println("리스트 출력");
          if (length == 0){
              System.out.println("빈 리스트");
          }
          for (int i = 0; i < length; i++) {
  
              System.out.println(now.getData());
  
          now = now.getNext();
          }
      }