Lecture/자료구조/2011/실습 3. 연결 리스트 연습

Single Linked List

ListNode.java

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

LinkedList.java

public class LinkedList {
 
    /** 리스트의 첫번째 노드를 가리키는 레퍼런스 변수 */
    private ListNode head;
 
    /**
     * 문자열 x를 리스트의 처음에 삽입한다.
     * @param x 삽입할 문자열
     */
    public void addFirstNode(String x) {
    }
 
    /**
     * 문자열 x를 리스트의 마지막에 삽입한다.
     * @param x 삽입할 문자열
     */
    public void addLastNode(String x) {
    }
 
    /**
     * 문자열 x를 리스트의 처음에 삽입한다.
     * @return 삭제할 첫번째 노드의 문자열
     */
    public String removeFirstNode() {
    }
 
    /**
     * 문자열 x를 리스트의 처음에 삽입한다.
     * @return 삭제할 마지막 노드의 문자열
     */
    public String removeLastNode() {
    }
 
    /**
     * 문자열 x를 리스트에서 찾는다.
     * @param x 찾고자 하는 문자열
     * @return 찾은 문자열 x를 가지고 있는 ListNode
     */
    public ListNode searchNode(String x) {
    }
 
    /**
     * 문자열 x를 p 노드 뒤에 삽입한다.
     * @param p 이 노드 뒤에 삽입한다.
     * @param x 삽입하고자 하는 문자열
     */
    public void insertNode(ListNode p, String x) {
    }
 
    /**
     * 인자로 받은 리스트를 추가한다.
     * @param list 삽입하고자 하는 리스트
     * @return 인자로 받은 문자열을 삽입한 자기 자신 리스트
     */
    public LinkedList addList(LinkedList list) {
    }
 
    /**
     * ListNode를 삭제한다.
     * @param p 삭제하고자 하는 ListNode
     */
    public void deleteNext(ListNode p) {
    }
 
    /**
     * 리스트를 역순으로 재배열한다.
     */
    public void reverse() {
    }
 
    /**
     * 리스트에 있는 내용을 출력한다.
     */
    public void printList() {   
        ListNode p;
        System.out.print("(");
        p = head;
        while (p != null) {
            System.out.print(p.data);
            p = p.link;
            if (p != null) {
                System.out.print(", ");
            }
        }
    }
 
    public static void main(String args[]) {
        LinkedList list = new LinkedList();
        list.addLastNode(“Kim”);
        list.addLastNode(“Lee”);
        list.addLastNode(“Park”);
        list.printList();     	        // (Kim, Lee, Park)가 프린트
        list.addLastNode(“Yoo”);   	// 원소 “Yoo”를 리스트 끝에 첨가
        list.printList();     	        // (Kim, Lee, Park, Yoo)가 프린트
 
        list.deleteLastNode();     
        list.printList();     	        // (Kim, Lee, Park)가 프린트
 
        list.reverse();
        list.printList();     	        // (Park, Lee, Kim)이 프린트
    }
 
}

Double Linked List

DoubleListNode.java

/**
 * 이중 연결 리스트에서 노드를 표현하기 위한 클래스이다.
 * 이 노드를 생성하면 기본적으로 모든 변수는 null이 된다.
 * Java에서는 변수의 값을 null로 설정하지 않아도 기본적으로 null이 된다.
 */
public class DoubleListNode {
    String data = null;
 
    DoubleListNode rlink = null;   // 다음 노드를 가리키는 레퍼런스 변수
    DoubleListNode llink = null;   // 이전 노드를 가리키는 레퍼런스 변수
}

DoubleLinkedList.java

public class DoubleLinkedList {
    /** 리스트의 첫 번째 노드를 가리키는 레퍼런스 변수 */
    DoubleListNode head = null;
 
    /** 리스트의 마지막 노드를 가리키는 레퍼런스 변수 */
    DoubleListNode tail = null;
 
    /** 리스트에 저장된 노드의 개수를 저장하고 있는 변수 */
    int length = 0;
 
    /**
     * 문자열 x를 리스트의 처음에 삽입한다.
     * @param x 삽입할 문자열
     */
    public void addFirstNode(String x) {
    }
 
    /**
     * 문자열 x를 리스트의 마지막에 삽입한다.
     * @param x 삽입할 문자열
     */
    public void addLastNode(String x) {
    }
 
    /**
     * 문자열 x를 리스트의 처음에 삽입한다.
     * @return 삭제할 첫번째 노드의 문자열
     */
    public String removeFirstNode() {
    }
 
    /**
     * 문자열 x를 리스트의 처음에 삽입한다.
     * @return 삭제할 마지막 노드의 문자열
     */
    public String removeLastNode() {
    }
 
    /**
     * 문자열 x를 리스트에서 찾는다.
     * @param x 찾고자 하는 문자열
     * @return 찾은 문자열 x를 가지고 있는 ListNode
     */
    public DoubleListNode searchNode(String x) {
    }
 
    /**
     * 문자열 x를 p 노드 뒤에 삽입한다.
     * @param p 이 노드 뒤에 삽입한다.
     * @param x 삽입하고자 하는 문자열
     */
    public void insertNode(DoubleListNode p, String x) {
    }
 
    /**
     * 인자로 받은 리스트를 추가한다.
     * @param list 삽입하고자 하는 리스트
     * @return 인자로 받은 문자열을 삽입한 자기 자신 리스트
     */
    public DoubleLinkedList addList(DoubleLinkedList list) {
    }
 
    /**
     * ListNode를 삭제한다.
     * @param p 삭제하고자 하는 ListNode
     */
    public void delete(DoubleListNode p) {
    }
 
    /**
     * 리스트를 역순으로 재배열한다.
     */
    public void reverse() {
    }
 
    /**
     * 리스트에 있는 내용을 출력한다.
     */
    public void printList() {   
        DoubleListNode p;
        System.out.print("(");
        p = head;
        while (p != null) {
            System.out.print(p.data);
            p = p.rlink;
            if (p != null) {
                System.out.print(", ");
            }
        }
    }
 
    public static void main(String args[]) {
        DoubleLinkedList list = new DoubleLinkedList();
        list.addLastNode(“Kim”);
        list.addLastNode(“Lee”);
        list.addLastNode(“Park”);
        list.printList();     	        // (Kim, Lee, Park)가 프린트
        list.addLastNode(“Yoo”);   	// 원소 “Yoo”를 리스트 끝에 첨가
        list.printList();     	        // (Kim, Lee, Park, Yoo)가 프린트
 
        list.deleteLastNode();     
        list.printList();     	        // (Kim, Lee, Park)가 프린트
 
        list.reverse();
        list.printList();     	        // (Park, Lee, Kim)이 프린트
    }
}