이중 연결 리스트에서 데이터 추가하는 4가지 방법

이중 연결 리스트의 시작 부분에 데이터 추가

  • 새 노드에 메모리를 할당하고 제공된 값을 해당 데이터 필드에 할당합니다.
  • 새 노드 이전 포인터를 null로 설정합니다.
  • 리스트가 비어있는 경우
    • 새로운 노드 다음 포인터를 null로 설정합니다.
    • 헤드를 새로운 노드로 업데이트합니다.
  • 리스트가 비어있지 않은 경우
    • 새로운 노드 다음 포인터를 현재 헤드로 설정합니다.
    • 현재 헤드의 이전 포인터를 새로운 노드로 변경합니다.
    • 헤드를 새로운 노드로 업데이트합니다.
static void push(int data) {
    Node newNode = new Node(data);

    newNode.next = head;

    if(head != null) head.prev = newNode;

    head = newNode;
}

 

지정된 노드 next에 노드를 추가하는 방법

노드가 주어지고 새로운 노드는 주어진 노드 next에 추가됩니다.

  • 먼저 새 노드를 만듭니다.
  • 새 노드에 데이터를 삽입합니다.
  • 새 노드 next를 지정된 노드 next로 변경합니다.
  • 지정된 노드 next를 새 노드로 변경합니다.
  • 새 노드 prev를 지정된 노드로 변경합니다.
  • 새 노드 next 노드의 prev를 새 노드로 변경합니다.
static void InsertAfter(Node prevNode, int data) {
    if(prevNode == null) {
        System.out.println("node null");
        return;
    }

    Node newNode = new Node(data);
    newNode.next = prevNode.next;
    prevNode.next = newNode;
    newNode.prev = prevNode;
    if(newNode.next != null) newNode.next.prev = newNode;
}

 

지정된 노드 prev에 노드를 추가하는 방법

  • 먼저 새 노드를 만듭니다.
  • 새 노드에 데이터를 삽입합니다.
  • 새 노드 prev를 지정된 노드 prev로 변경합니다.
  • 지정된 노드 prev를 새 노드로 변경합니다.
  • 새 노드 next를 지정된 노드로 변경합니다.
  • 새 노드 prev가 null이면 헤드이므로 헤드를 새 노드로 업데이트합니다.
  • 새 노드 prev가 null이 아니면 새 노드 prev 노드에 next를 새 노드로 변경합니다.
static void InsertBefore(Node nextNode, int data) {
    if(nextNode == null) {
        System.out.println("node null");
        return;
    }

    Node newNode = new Node(data);
    newNode.prev = nextNode.prev;
    nextNode.prev = newNode;
    newNode.next = nextNode;

    if(newNode.prev != null) newNode.prev.next = newNode;
    else head = newNode;
}

 

이중 연결 리스트 끝에 데이터를 추가하는 방법

새 노드는 항상 주어진 연결 리스트 마지막 노드 뒤에 추가됩니다.

  • 먼저 새 노드를 만듭니다.
  • 새 노드에 데이터를 삽입합니다.
  • 새 노드 next를 null로 만듭니다.
  • 리스트가 비어있으면 헤드를 새 노드로 변경합니다.
  • 그렇지 않으면 리스트의 끝으로 이동합니다.
  • 마지막 노드의 next를 새 노드로 변경합니다.
  • 새 노드의 prev를 마지막 노드로 변경합니다.
static void append(int data) {
    Node newNode = new Node(data);
    Node last = head;

    if(head == null) {
        head = newNode;
        return;
    }

    while(last.next != null) last = last.next;

    last.next = newNode;
    newNode.prev = last;
}