[Data Structure] 단순 연결 리스트

순차표현의 장점으로 표현이 간단하다는 것과 원소의 접근이 빠르다는 것(random access)이 있다.하지만 단점으로는 원소를 중간에 삽입, 삭제가 어렵고 저장공간의 낭비와 효율성적으로 문제가 있다.

연결표현

비순차 표현: 원소의 물리적 순서와 논리적 순서가 일치하지 않아도 되며 다음 원소에 대한 주소를 저장하고 있다.

하나의 노드는 데이터 필드와 링크 필드를 가지고 있다.

 

class ListNode {
    String data;
    ListNode link;
}

ListNode startNode, p1, p2;
p1 = new ListNode();
p2 = new ListNode();

p1.data = "첫번째 데이터";
p2.data = "두번째 데이터";

p1.link = p2;
p2.link = null;

startNode = p1

여기서 startNode, p1, p2는 참조 변수이며 생성된 객체에 대한 주소값을 가지고 있다.

원소의 삽입

원소의 삭제

ListNode

1. ListNode class

public class ListNode {
    String data;
    ListNode link;

    public ListNode() {
        data = null;
        link = null;
    }
    public ListNode(String val) {
        data = val;
        link = null;
    }
    public ListNode(String val, ListNode p) {
        data = val;
        link = p;
    }
}

2. LinkedList class

리스트가 처음을 가리킬 head 변수를 가지고 있다.

public class LinkedList{
    private ListNode head;

    // methods
}

3. 처음 노드를 삽입하는 경우

새로운 노드를 만든 뒤 head가 새로 만들어진 newNode를 가리키게 한다.

public void addFirstNode(String x) {
    ListNode newNode = new ListNode();
    newNode.data = x;
    newNode.link = head;
    head = newNode;
}

4. p가 가리키는 노드 다음에 리스트 노드 삽입

p가 가리키는 노드 뒤에 삽입하기 위해서는 총 3가지를 확인해볼 필요가 있다.

• 리스트가 빈 리스트인지
• p가 가리키는 노드가 있는지
• p가 가리키는 노드가 있는지

public void insertNode(ListNode p, String x) {
    ListNode newNode = new ListNode();
    newNode.data = x;
    // ListNode newNode = new ListNode(x);

    if (head == null) { // 공백 리스트인 경우
        head = newNode;
        newNode.link = null;
    } else if (p == null) { // p가 null이면 리스트의 첫 번째 노드로 삽입
        newNode.link = head;
        head = newNode;
    } else { // p가 가리키는 노드의 다음 노드로 삽입
        newNode.link = p.link;
        p.link = newNode;
    }
}

5. 마지막 노드로 삽입

리스트의 head 부터 시작하여 연결된 노드를 쭉 타고 가다 마지막 노드임을 알게 되면(link == null) 추가한다. 1가지만 확인하면 된다.

• 리스트가 비어 있는지

public void addLastNode(String x) {
    ListNode newNode = new ListNode(); // 새로운 노드 생성
    newNode.data = x;
    newNode.link = null;
    if (head == null) {
        head = newNode;
        return;
    }
    ListNode p = head; // p
    는 임시 순회 레퍼런스 변수
    while (p.link != null) { // 마지막 노드를 탐색
        p = p.link;
    }
    p.link = newNode; // 마지막 노드로 첨가
}

6. 두개의 리스트를 합치기

고려해볼 문제가 1가지 있다. 문제가 없다면 리스트 하나의 마지막 노드를 다른 리스트 처음과 연결해주면 된다.

• 합치려고 하는 리스트 중 빈 리스트가 있는지

public LinkedList addList(LinkedList list) {
    if (head == null) {
        head = list.head;
        return this;
    } 
    else if (list.head == null) {
        return this;
    } 
    else {
    // p는 임시 순회 포인터
        ListNode p = head; 
        while(p.link != null){
            p = p.link;
        }
        p.link = list.head;
        return this;        
    }
}

7. 리스트에서 특정 원소값 찾기

for (ListNode p = head; p != null; p = p.link) {
    if (x.equals(p.data)) return p;
}

public ListNode searchNode(String x) {
    ListNode p = head; // p는 임시 포인터
    while (p != null) {
        if (x.equals(p.data))// 원소 값이 x인 노드를 발견
        return p;
        p = p.link;
    }
    return p; // 원소 값이 x인 노드가 없는 경우 null을 반환
}

8. p가 가리키는 다음 노드 삭제

이 상황도 고려해야될 문제가 2가지 있다.

• 리스트가 비었는지
• p가 가리키는 노드가 있는지

p가 가리키는 노드가 없다면 첫번째 노드를 삭제한다는 것은 이 리스트의 특별한 룰로 생각하면 될것 같다.

public void deleteNext(ListNode p) {
    if (head == null) // head가 null이면 에러
        throw new NullPointerException();
    if (p == null) // p가 null이면 첫 번째 노드 삭제
        head = head.link;
    else {
        ListNode q = p.link;
        if (q == null) // 삭제할 노드가 없는 경우
            return;
        p.link = q.link;
    }
}

9. 리스트의 마지막 노드 삭제

여기서도 고려해야될 문제가 2가지 있다.

• 리스트가 비었는지
• 리스트의 원소가 하나이상인지

public void deleteLastNode() {
    ListNode previousNode,
    currentNode;
    if (head == null) 
        return;
    if (head.link == null) { // 원소가 하나 밖에 없는 경우
        head = null;
        return;
    } else {
        previousNode = head;
        currentNode = head.link;
        while (currentNode.link != null) {
            previousNode = currentNode;
            currentNode = currentNode.link;
        }
        previousNode.link = null;
    }
}

10. 연결리스트 프린트

while 문으로 찾거나 for문으로 찾는 방법이 있을 것 같다.

public void printList() {
        ListNode p = head;        
        while (p != null) {
            System.out.print(p.data);
            p = p.link;
            if (p != null) {
                System.out.print(", ");
            }
        }       
    )
}