[자료구조] 리스트-2

본문과 관련하여 실습한 전체코드는 리파지토리에 별도 작성하였습니다.: https://github.com/ejImDev/data_structure_study.git

이중연결리스트

각 노드가 두 개의 레퍼런스를 가지고 각각 이전노드와 다음 노드를 가리키는 연결리스트
단순연결리스트는 삽입,삭제시 반드시 이전노드를 가리키는 레퍼런스를 추가로 알아내야 하고, 역방향 노드를 탐색할 수 없었음
이중연결리스트는 이런 단점을 보완하나, 각 노드마다 추가 레퍼런스를 저장해야한다는 단점이 있음

이중연결리스트로 구현한 리스트 만들기 (C)

DNode 클래스

public class DNode<E> {
private E item;
private DNode previous;
private DNode next;
public DNode(E newItem, DNode p, DNode q){
 item = newItem;
 previous = p;
 next = q;
}
public E getItem() { return item; }
public DNode getPrevious() { return previous; }
public DNode getNext() { return next; }
public void setItem(E newItem) { item = newItem; }
public void setPrevious(DNode p) { previous = p; }
public void setNext(DNode q) { next = q; }

DList 클래스

public class DList<E> {
 protected DNode head, tail;
 protected int size;
 public DList(){
     head = new DNode (null,null,null);
     tail = new DNode (null,head,null);
     head.setNext(tail);
     size = 0;
 }
 ...
}

구현 메소드

insertBefore (지정 노드 전에 삽입)

public void insertBefore(DNode p, E newItem){
 DNode t = p.getPrevious();
 DNode newNode = new DNode(newItem, t, p);
 p.setPrevious(newNode);
 t.setNext(newNode);
 size++;
}

insertAfter (지정 노드의 다음에 삽입)

public void insertAfter (DNode p, E newItem){
  DNode t = p.getNext();
  DNode newNode = new DNode(newItem, p, t);
  t.setPrevious(newNode);
  p.setNext(newNode);
  size++;
}

delete (지정 노드 삭제)

public void delete(DNode x){
  if(x==null) {
      throw new NoSuchElementException();
  }
  DNode f = x.getPrevious();
  DNode r = x.getNext();
  r.setPrevious(f);
  f.setNext(r);
  size--;
}

C 정리

이중연결리스트에서 삽입이나 삭제 연산은 각각 상수개의 레퍼런스만을 갱신하므로 O(1)시간 수행
탐색 연산은 head 또는 tail로부터 노드들을 순차적으로 탐색해야 하므로 O(N)시간 수행

환형연결리스트

마지막 노드가 첫 노드와 연결된 단순연결리스트
마지막 노드의 레퍼런스가 저장된 last가 단순연결리스트의 head와 같은 역할
마지막 노드와 첫 노드를 O(1) 시간에 방문할 수 있는 장점
리스트가 empty가 아니면 어떤 노드도 null 레퍼런스를 가지고 있지 않으므로 프로그램에서 null 조건 검사를 하지않아도 됨
반대방향으로 방문하기 쉽지 않으며, 무한 루프가 발생할 수 있음

원형연결리스트로 구현한 리스트 만들기 (D)

CList 클래스

public class CList<E> {
 private Node last;
 private int size;
 public CList(){
     last = null;
     size = 0;
 }
}

Node 클래스 : 단순연결리스트의 Node와 동일

이 외 코드

insert

public void insert(E newItem) {
 Node newNode = new Node(newItem, null);
 if(last==null){
   newNode.setNext(newNode);
   last=newNode;
 } else {
   newNode.setNext(last.getNext));
   last.setNext(newNode);
 }
 size++;
}

delete

public void delete() {
  if(isEmpty()){
      throw new NoSuchElementException();
  } 
  Node x = last.getNext();
  if(x==last) {
      last = null;
  } else {
      last.setNext(x.getNext());
      x.setNext(null);
  }
  size--;
  return x;
}

D 정리

삽입이나 삭제 연산은 각각 상수개의 레퍼런스만을 갱신하므로 O(1)시간 수행
탐색 연산은 순차적으로 탐색해야 하므로 O(N)시간 수행

A,B,C,D 최악의 경우 수행시간 비교

| 자료구조 | 접근 | 탐색 | 삽입 | 삭제 | 비고 | |–|–|–|–|–|–| | 1차원 배열 | O(1) | O(N) | O(N) | O(N) | 정렬된 배열에서 탐색은 O(logN) | | 단순연결리스트 | O(N) | O(N) | O(1) | O(1) |삽입될 노드의 이전 노드 레퍼런스가 주어진 경우 | | 이중연결리스트 | O(N) | O(N) | O(1) | O(1) |삽입될 노드의 이전 노드 레퍼런스가 주어진 경우 | | 환형연결리스트 | O(N) | O(N) | O(1) | O(1) |삽입될 노드의 이전 노드 레퍼런스가 주어진 경우 |

참고 자료 : ‘경기대학교 소프트웨어중심대학사업단 - JAVA 자료구조’ https://youtu.be/3o2u3_XvSbU

IM