자료구조(Data Structure) 연결리스트 (Linked List) 기본 정리

Linked List

---

연속적인 메모리 위치에 저장되지 않는 선형 데이터 구조

 

(포인터를 사용해서 연결된다)

 

각 노드는 데이터 필드와 다음 노드에 대한 참조를 포함하는 노드로 구성

 

왜 Linked List를 사용하나?

배열은 비슷한 유형의 선형 데이터를 저장하는데 사용할 수 있지만 제한 사항이 있음

1. 배열의 크기가 고정되어 있어 미리 요소의 수에 대해 할당을 받아야 함

2. 새로운 요소를 삽입하는 것은 비용이 많이 듬 (공간을 만들고, 기존 요소 전부 이동)

장점

1. 동적 크기

2. 삽입/삭제 용이

단점

1. 임의로 액세스를 허용할 수 없음. 즉, 첫 번째 노드부터 순차적으로 요소에 액세스 해야함 (이진 검색 수행 불가능)

2. 포인터의 여분의 메모리 공간이 목록의 각 요소에 필요

노드 구현은 아래와 같이 데이터와 다음 노드에 대한 참조로 나타낼 수 있다

// A linked list node 
struct Node 
{ 
  int data; 
  struct Node *next; 
}; 

Single Linked List

노드 3개를 잇는 코드를 만들어보자

      head         second         third 
        |             |             | 
        |             |             | 
    +---+---+     +---+---+     +----+----+ 
    | 1  | o----->| 2 | o-----> |  3 |  # | 
    +---+---+     +---+---+     +----+----+

 

 

노드 추가

• 앞쪽에 노드 추가

void push(struct Node** head_ref, int new_data){
    struct Node* new_node = (struct Node*) malloc(sizeof(struct Node));

    new_node->data = new_data;

    new_node->next = (*head_ref);

    (*head_ref) = new_node;
}

• 특정 노드 다음에 추가

void insertAfter(struct Node* prev_node, int new_data){
    if (prev_node == NULL){
        printf("이전 노드가 NULL이 아니어야 합니다.");
        return;
    }

    struct Node* new_node = (struct Node*) malloc(sizeof(struct Node));

    new_node->data = new_data;
    new_node->next = prev_node->next;

    prev_node->next = new_node;
    
}

• 끝쪽에 노드 추가

void append(struct Node** head_ref, int new_data){
    struct Node* new_node = (struct Node*)malloc(sizeof(struct Node));

    struct Node *last = *head_ref;

    new_node->data = new_data;

    new_node->next = NULL;

    if (*head_ref == NULL){
        *head_ref = new_node;
        return;
    }

    while(last->next != NULL){
        last = last->next;
    }

    last->next = new_node;
    return;

}

 

소스코드 (Java)

 

LinkedList.java

class LinkedList {
    
    Node head;

    static class Node {
        int data;
        Node next;
        Node(int d) { // 생성자
            data = d; next = null;
        }
    }

    public void printList() { 
        Node n = head; 
        while (n != null) { 
            System.out.print(n.data+" "); 
            n = n.next; 
        } 
    }

    public static void main(String[] args) {

        LinkedList llist = new LinkedList();

        llist.head = new Node(1);
        Node second = new Node(2);
        Node third = new Node(3);

        /*
          llist.head        second              third 
             |                |                  | 
             |                |                  | 
         +----+------+     +----+------+     +----+------+ 
         | 1  | null |     | 2  | null |     |  3 | null | 
         +----+------+     +----+------+     +----+------+ 
        */
    
        llist.head.next = second; // 첫번째 노드에 두번째 노드 연결
        second.next = third; // 두번째 노드에 세번째 노드 연결
        
        /*
  
         llist.head        second              third 
            |                |                  | 
            |                |                  | 
        +----+------+     +----+------+     +----+------+ 
        | 1  |  o-------->| 2  |  o-------->|  3 | null | 
        +----+------+     +----+------+     +----+------+ 
        
        */
        llist.printList(); 
    }
}

 

Push 버전

LinkedList.java

class LinkedList 
{ 
    Node head;
  
    class Node 
    { 
        int data; 
        Node next; 
        Node(int d) {data = d; next = null; } 
    } 
  
    public void push(int new_data) 
    { 
        Node new_node = new Node(new_data); 
  
        new_node.next = head; 
  
        head = new_node; 
    } 
  
    public void insertAfter(Node prev_node, int new_data) 
    { 
        if (prev_node == null) 
        { 
            System.out.println("The given previous node cannot be null"); 
            return; 
        } 
  
        Node new_node = new Node(new_data); 
  
        new_node.next = prev_node.next; 
  
        prev_node.next = new_node; 
    } 
     
    public void append(int new_data) 
    { 
        Node new_node = new Node(new_data); 
  
        if (head == null) 
        { 
            head = new Node(new_data); 
            return; 
        } 

        new_node.next = null; 
  
        Node last = head;  
        while (last.next != null) 
            last = last.next; 
  
        last.next = new_node; 
        return; 
    } 
  
    public void printList() 
    { 
        Node tnode = head; 
        while (tnode != null) 
        { 
            System.out.print(tnode.data+" "); 
            tnode = tnode.next; 
        } 
    } 
  
    public static void main(String[] args) 
    { 
        LinkedList llist = new LinkedList(); 
  
        //6->NUllist 
        llist.append(6); 
        
        // 7->6->NUllist 
        llist.push(7); 
     
        // 1->7->6->NUllist 
        llist.push(1); 

        // 1->7->6->4->NUllist 
        llist.append(4); 

        // 1->7->8->6->4->NUllist 
        llist.insertAfter(llist.head.next, 8); 
  
        System.out.println("\nCreated Linked list is: "); 
        llist.printList(); 
    } 
}