[Data Structure] 자료구조 - 연결 리스트(Linked List) - 단순 연결 리스트(Singly / Linear Linked List)

1. 연결 자료구조

개념: 순차 선형 리스트(배열)는 논리적인 순서와 물리적인 순서가 같기 때문에

원소의 위치를 찾아 액세스하기 쉽다는 장점이 있지만,

삽입 연산이나 삭제 연산에 

원소들을 이동시키는 추가적인 작업과 시간이 필요함.

원소의 개수가 많고, 삽입, 삭제 연산이 많이 발생하는 경우에는

 원소들의 이동 작업으로 인한 오버헤드가 증가함.

결국, 메모리 사용의 비효율성의 문제를 갖음.

이로 인한 문제를 개선한게 바로 

연결 자료구조!!!

각 원소에 저장되어 있는 다음 원소의 주소에 대한 참조에 의해서

연결되는 방식!

효율적으로 메모리 사용을 할 수 있다!

종류: 

단순 연결 리스트, 원형 연결 리스트, 이중 연결 리스트, 이중 원형 연결 리스트

1-1. 노드

개념: 연결 자료구조 방식에서 원소는 연결될 다음 원소에 대한 주소를 저장해야 하기 때문에,

<원소, 주소>

단위로 저장해야 함.

이러한 단위 구조를 노드라 한다!!

노드는 아래 그림과 같이 구성되어 있습니다!

 

 

원소의 값을 저장하는 데이터 필드(Data Field)

다음 노드의 주소를 저장하는 링크 필드(Link Field)

2. 단순 연결 리스트(Singly Linked List)

노드가 하나의 링크 필드에 의해서

다음 노드와 연결되는 구조를 가진 연결 리스트

2-1. 삽입 연산

자 보기 쉽게 설명을 해드리겠습니다!!

진짜사나이들이 기차놀이를 한다고 가정합시다~

 

위처럼 서경석은 샘의 이름을 알고있고,

샘은 형식의 이름을 알고있습니다.

서로 연결되어있는거죠~ 

기차처럼!!

근데 갑자기 헨리가 같이 하고 싶다고 

서경석과 샘의 사이로 끼어 드는 거죠!!!

 

사이로 끼어 드려고 하는 헨리 때문에...

서경석 뒤에는 헨리가 들어오고

헨리 뒤가 샘이겠네요??

그럼 먼저 헨리가 서경석이 가지고 있던 샘의 이름을 넘겨 받습니다!

아래처럼~

그리고 서경석은 뒤에 헨리가 있다는 것을 가지고 있어야 겠죠??

 

위 처럼 기차가 한줄이 늘어나게 됩니다~

이렇게 삽입 연산을 표현할수 있겠네요~

알고리즘을 Pesudo Code로 보시겠습니다!

여기서 삽입은 중간 노드에 삽입이 되는 겁니다~

 

/*
    * L: 연결 리스트
    * pre: 앞 노드
    * x: 입력할 데이터 값
*/
 
insertMiddleNode(L, pre, x) {
    new <- getNode();
    new.data <- x;
    
    if (L == NULL) then {
        L <- new;
        new.link <- null;
    } else {
        new.link <- pre.link;
        pre.link <- new;
    }
}

다음은 삭제 연산입니다!

2-2. 삭제 연산

잘 놀다가 헨리가 쉽게 질려버렸네요~

이제 그만하고 쉬겠다고 합니다!

헨리가 빠지면, 다시 서경석 뒤는 샘이겠네요~????

헨리가 가지고 있던 뒷 사람 이름을 앞사람(서경석)에게 넘겨주고 빠지게 됩니다!

 

다시 이렇게 바뀝니다!!!

알고리즘을 Pesudo Code로 보시겠습니다!

 

 
/*
    * L: 연결 리스트
    * pre: 삭제 할 노드의 앞 노드
*/
 
deleteNode(L, pre) {
    if (L == NULL) then error;
    else {
        old <- pre.link;
        if (old == null) then return;
        pre.link <- old.link;
    }
    free old;
}

삭제를 하고자하는 노드의 앞노드를 넘겨줘야 합니다!!!

삭제할 앞노드의 링크를 old로 담아서

old의 링크를 앞 노드의 링크로 넘겨주고

old는 메모리를 반환하게 되는 거죠~

자 그럼, 간단한 예제를 통해 확인해 보도록 합시다!!

자바로 작성된 String 값을 data로 두어서 예제를 만들어 보았습니다!

클래스 다이어 그램입니다!

 

ListNode.java

 

package single;
 
public class ListNode {
    private String data;
    private ListNode link;
 
    // 생성자
    public ListNode() {
        this.data = null;
        this.link = null;
    }
 
    public ListNode(String data) {
        this.data = data;
        this.link = null;
    }
 
    public ListNode(String data, ListNode link) {
        this.data = data;
        this.link = link;
    }
 
    // Getter & Setter
    public String getData() {
        return data;
    }
 
    public void setData(String data) {
        this.data = data;
    }
 
    public ListNode getLink() {
        return link;
    }
 
    public void setLink(ListNode link) {
        this.link = link;
    }
}
 

SingleLinkedList.java

 

 
package single;
 
public class SingleLinkedList {
    private ListNode head;
 
    // 생성자
    public SingleLinkedList() {
        head = null;
    }
 
    // 중간 노드 삽입
    public void insertMiddleNode(ListNode pre, String data) {
        ListNode newNode = new ListNode(data);
        newNode.setLink(pre.getLink()); // 삽입할 노드에 이전 노드의 참조 값 넘김
        pre.setLink(newNode); // 이전 노드의 참조 값을 삽입할 노드로 지정
    }
 
    // 마지막 노드에 삽입
    public void insertLastNode(String data) {
        ListNode newNode = new ListNode(data);
 
        // 리스트가 비어있으면 헤드로 지정
        if (head == null) {
            this.head = newNode;
        } else {
            ListNode tmp = head;
            while (tmp.getLink() != null)
                // 마지막 원소일때까지 탐색
                tmp = tmp.getLink();
            tmp.setLink(newNode);
        }
    }
 
    public void deleteNode(ListNode pre) {
        if (head == null) {
            System.out.println("리스트가 비어있습니다!");
            return;
        } else {
            ListNode old = pre.getLink(); // 삭제할 노드 가져와 old로 지정
            if (old == null)
                return;
            pre.setLink(old.getLink());
        }
    }
 
    public void deleteLastNode() {
        ListNode pre, tmp;
 
        if (head == null) {
            System.out.println("리스트가 비어있습니다!");
            return;
        }
 
        if (head.getLink() == null) {
            head = null;
        } else {
            pre = head;
            tmp = head.getLink();
 
            // 마지막 노드의 이전 노드의 링크가 널인 값인지 까지 탐색
            while (tmp.getLink() != null) {
                pre = tmp;
                tmp = tmp.getLink();
            }
 
            pre.setLink(null);
        }
    }
 
    public ListNode searchNode(String data) {
        ListNode tmp = this.head;
 
        while (tmp != null) {
            if (data == tmp.getData())
                return tmp;
            else
                tmp = tmp.getLink();
        }
 
        return tmp;
    }
 
    public void reverseList() {
        ListNode next = head;
        ListNode current = null;
        ListNode pre = null;
 
        while (next != null) {
            pre = current;
            current = next;
            next = next.getLink();
            current.setLink(pre);
        }
 
        head = current;
    }
 
    public void printList() {
        ListNode tmp = this.head;
        System.out.print("L = (");
 
        while (tmp != null) {
            System.out.print(tmp.getData());
            tmp = tmp.getLink();
 
            if (tmp != null) {
                System.out.print(", ");
            }
        }
 
        System.out.println(")");
    }
}
 

SingleMain.java

 

 
package single;
 
public class SingleMain {
    public static void main(String[] args) {
        SingleLinkedList L = new SingleLinkedList();
 
        System.out.println("(1) 공백 리스트에 노드 4개 삽입하기");
        L.insertLastNode("월");
        L.insertLastNode("화");
        L.insertLastNode("목");
        L.insertLastNode("금");
 
        L.printList();
 
        System.out.println("(2) 화 노드 뒤에 수 노드 삽입하기");
        ListNode pre = L.searchNode("화");
        if (pre == null) {
            System.out.println("검색 실패!! ");
        } else {
            L.insertMiddleNode(pre, "수");
            L.printList();
        }
 
        System.out.println("(3) 화 노드 삭제 하기");
        pre = L.searchNode("월");
        L.deleteNode(pre);
        L.printList();
 
        System.out.println("(4) 마지막 노드 삭제하기");
        L.deleteLastNode();
        L.printList();
    }
}
 

결과는 아래와 같습니다!!