[자료구조] - 연결 리스트(Linked List)[1]

연결리스트(Linked List)란

 

연결리스트(Liked List)는 데이터 요소들을 순차적으로 저장하는 선형 자료구조이다.

각 요소는 데이터와 다음 요소를 가리키는 포인터로 이루어져 있다. 따라서 연결 리스트는 메모리에서 연속적으로 할당되지 않는 노드들이 포인터를 통해 연결되어 있는 형태를 가지고 있다.

 

핵심 특징

동적할당	요소를 추가하거나 삭제할 때마다 필요한 만큼의 메모리를 동적으로 할당하므로, 크기가 동적으로 조절될 수 있다.
삽입 및 삭제 용이성	요소의 삽입 및 삭제가 쉽다. 요소를 삽입할 때는 새로운 요소를 추가하고, 삭제할 때는 해당 요소를 연결에서 제거하면 된다.
메모리의 효율성	연결 리스트는 데이터 요소들이 메모리에서 연속적으로 배치되지 않기 때문에, 데이터 요소들 간의 간격이 듀오적으로 조절될 수 있다. 이로인해 메모리의 효율성이 떨어질 수 있다.
순차적인 접근	연결 리스트는 요소들이 메모리상에서 순차적으로 배치되지 않기 때문에 요소들에 대한 순차적인 접근이 배열(Array)에 비해 상대적으로 느릴 수 있다.

 

 

단일 연결 리스트(Singly Linked List)

 

 

단일 연결 리스트(Singly Linked List)는 각 노드가 데이터와 다음 노드를 가리키는 포인터로 이루어진 연결 리스트이다. 각노드는 데이터와 다음 노드를 가리키는 포인터로 이루어져 있으며 마지막 노드의 포인터는 null을 가리킨다.

 

단일 연결 리스트의 특징

• 각 노드는 데이터와 다음 노드를 가리키는 포인터로 이루어져 있다.
• 연속적인 메모리 공간을 사용하지 않는다.
• 역방향 접근이 불가능 하다.
• 삽입 및 삭제연산이 효율적이다.

 

 

코드로 구현(JAVA)

class Node{
    // 데이터
    int data;
    // 다음 노드를 가르킴.
    Node next;

    public Node(int data) {
        this.data = data;
        this.next = null;
    }
}

public class SinglyLinkedList {
    private Node head;

    public SinglyLinkedList() {
        this.head = null;
    }

    /*
    * append 삽입하기
    * */
    public void append(int data){
        // 노드 생성, 새로운 데이터 삽입
        Node newNode = new Node(data);

        // 헤드가 없다면 새로운 노드를 헤드로 지정후 리턴
        if(head == null) {
            head = newNode;
            return;
        }

        // 헤드를 기준으로 잡는다.
        Node current = head;

        // 다음 노드가 널인 노드를 찾기
        while(current.next != null) {
            current = current.next;
        }

        //새로운 데이터를 다음 노드를 지정
        current.next = newNode;

    }

    // 현재 리스트의 이전으로 삽입
    public void prepend(int data) {
        Node newNode = new Node(data);

        //현재 헤드를 새로운노드의 다음노드로 지정
        newNode.next = head;
        //현재 데이터를 헤드로 바꿈
        head = newNode;
    }


    // 지정 데이터 삭제
    public void delete(int data){

        // 헤드가 없으면 데이터가 없음
        if(head == null) return;

        // 헤드의 데이터가 삭제 데이터랑 같으면
        if(head.data == data){
            // 헤드의 다음데이터가 헤드가 된다.
            head = head.next;
            return;
        }

        // 기준점 헤드 생성
        Node current = head;
        // 이전의 데이터 저장용
        Node prev = null;

        // 헤드가 널이 아니고, 현재 데이터가 삭제할 데이터와 같지 않을때 까지
        while (current != null && current.data != data){
            prev = current;
            current = current.next;
        }

        // 헤드가 없으면 그냥 리턴
        if (current == null) return;
        // 삭제한 데이터 이전의 데이터를 연결
        prev.next = current.next;
    }

    public void printer(){
        Node current = head;
        while ( current != null){
            System.out.printf(current.data + " -> ");
            current = current.next;
        }
        System.out.println("null");
    }
}

 

이중 연결 리스트(Doubly Linked List)

이중 연결 리스트(Doubly Linked List)는 각 노드가 데이터, 이전 노드를 가리키는 포인터, 다음 노드를 가리키는 포인터로 이루어진 연결 리스트이다. 각 노드는 데이터와 이전 노드를 가리키는 포인터, 그리고 다음 노드를 가리키는 포인터로 이루어져 있으며, 마지막 노드와 첫 번째 노드 사이의 연결이 순환 될 수도 있다.

 

이중 연결 리스트의 특징

• 각 노드는 데이터와 이전 노드를 가리키는 포인터, 다음 노드를 가리키는 포인터로 이루어져 있따.
• 역방향 접근이 가능하다.
• 양방향으로 삽입 및 삭제 연산이 효율적이다.
• 연속적인 메모리 공간을 사용하지 않는다.
• 마지막 노드와 첫 번째 노드 사이의 연결이 순환 될 수 있다

 

코드로 구현(JAVA)

package LinkedList;

class Node{
    int data;
    Node prev;
    Node next;

    public Node(int data) {
        this.data = data;
        this.prev = null;
        this.next = null;
    }

}

public class DoublyLinkedList {
    private Node head;
    private Node tail;

    public DoublyLinkedList(Node head, Node tail) {
        this.head = head;
        this.tail = tail;
    }

    // 삽입
    public void append(int data){
        Node newNode = new Node(data);

        //리스트에 데이터가 없을때
        if(head == null){
            head = newNode;
            tail = newNode;
            return;
        }

        /*
        * 테일 데이터를 새로운 데이터로 바꾼 뒤, 새로운 데이터를 테일 데이터로 지정
        * */
        tail.next = newNode;
        newNode.prev = tail;
        tail = newNode;
    }

    // 헤드로 삽입

    public void prepend(int data) {
        Node newDoubleNode = new Node(data);
        if(head == null){
            head = newDoubleNode;
            tail = newDoubleNode;
            return;
        }

        /*
        * 기존헤드를 삽입데이터로 변경하기
        * */
        newDoubleNode.next = head;
        head.prev = newDoubleNode;
        head = newDoubleNode;
    }

    // 지정 데이터 삽입
    public void delete(int data){
        if(head == null) return;

        // 삭제데이터가 첫데이터면 헤드를 변경
        if(head.data == data){
            head = head.next;
            if(head != null) head.prev = null;
            return;
        }

        //삭제데이터가 끝데이터면 테일을 변경
        if(tail.data == data){
            tail = tail.prev;
            tail.next = null;
            return;
        }

        // 헤드부터 순회하기
        Node current = head;
        // current가 null 이거나, 데이터가 같으면 멈춘다.
        while (current !=null && current.data != data){
            current = current.next;
        }

        //헤드가 없으면 리턴
        if(current == null) return;

        // 삭제된 데이터의 이전, 다음데이터의 연결
        current.prev.next = current.next;
        current.next.prev = current.prev;

    }
	
    // 순서대로 출력
    public void ForwardPrinter() {
        Node current = head;
        while (current != null) {
            System.out.print(current.data + " <-> ");
            current = current.next;
        }
        System.out.println("null");
    }
	
    //역방향으로 출력
    public void BackwardPrinter() {
        Node current = tail;
        while (current != null) {
            System.out.print(current.data + " <-> ");
            current = current.prev;
        }
        System.out.println("null");
    }
}

 

---

원형 연결리스트, 이중 원형 연결리스트는 다음 포스팅에서 게시하겠습니다.