LinkedList 구현

1. LinkedList 특징

---

• 동일한 데이터 타입을 순서에 따라 관리
• 노드에는 자료와 다음 요소를 가르키는 링크가 있음.
• 자료가 추가될 때 노드 만큼의 메로리 할받 받고이전 노드의 링크로 연결.
• 연결 리스트의 i번 째 요소를 찾는데 필요한 시간은 요소의 수에 비례 O(n)
• jdk : LinkedList

 

 

2. LinkedList 구현

2.1 Node

---

• Data와 다음 노드에 대한 정보(참조)를 가지고 있음.

public class MyListNode {

    private String data;
    private MyListNode next;

    public MyListNode() {
        data = null;
        next = null;
    }

    public MyListNode(String data){
        this.data = data;
        this.next = null;
    }

    public MyListNode(String data, MyListNode next) {
        this.data = data;
        this.next = next;
    }

    public String getData() {
        return data;
    }

    public MyListNode getNext() {
        return next;
    }

    public void setNext(MyListNode next) {
        this.next = next;
    }
}

 

 

2.2 LinkedList

---

•  count : list의 수, 다음에 data 들어갈 수 있는 max position 값
• 조회, 삭제, 삽입 시 0<= position <= count

public class MyLinkedList {

    private MyListNode head;
    private int count;

    public MyLinkedList(){
        head = null;
        count = 0; //size, 다음 들어갈 수 있는 max position
    }

    public MyListNode addElement(String data){

        MyListNode newNode = new MyListNode(data);

        if (head == null){
            head = newNode;
        }
        else {
            MyListNode temp = head;
            while (temp.getNext() != null){
                temp = temp.getNext();
            }

            //temp의 다음이 null인 경우
            temp.setNext(newNode);
        }

        count++;
        return newNode;
    }

    public MyListNode insertElement(int position, String data){

        MyListNode tempNode = head;
        MyListNode preNode = new MyListNode();

        MyListNode newNode = new MyListNode(data);

        if(position < 0 || position > count){
            throw new IllegalArgumentException("해당 위치에 insert 불가");
        }

        //맨 앞에 추가하는 경우
        if (position == 0){
            newNode.setNext(head);
            head = newNode;
        }else {
            preNode = findPreNode(position, tempNode, preNode);
            //temp는 기존 position을 가르킴.
            newNode.setNext(preNode.getNext());
            preNode.setNext(newNode);

        }

        count++;
        return newNode;
    }

    public void removeElement(int position){
        MyListNode tempNode = head;
        MyListNode preNode = new MyListNode();

        if(position < 0 || position > count){
            throw new IllegalArgumentException("position 오류");
        }
        //맨 앞을 지우는 경우
        if(position == 0){
            head = tempNode.getNext();
        }else {
            //find PreNode
            preNode = findPreNode(position, tempNode, preNode);
            MyListNode nextNode = preNode.getNext().getNext();
            //temp노드는 입력된 position에 해당.
            preNode.setNext(nextNode);
        }

        count--;
    }

    public String getElement(int position){
        MyListNode tempNode = head;

        if (position < 0 || position > count){
            throw new IllegalArgumentException("position 오류 현재 list수는 " + count + "개 입니다.");
        }
        if (position == 0){
            return head.getData();
        }

        for (int i = 0; i < position; i++){
            tempNode = tempNode.getNext();
        }

         return tempNode.getData();
    }

    public MyListNode getNode(int position){
        MyListNode tempNode = head;

        if (position < 0 || position > count){
            throw new IllegalArgumentException("position 오류 현재 list수는 " + count + "개 입니다.");
        }
        if (position == 0){
            return head;
        }

        for (int i = 0; i < position; i++){
            tempNode = tempNode.getNext();
        }

        return tempNode;
    }

    private MyListNode findPreNode(int position, MyListNode tempNode, MyListNode preNode) {
        for (int i = 0; i < position; i++){
            preNode = tempNode;
            tempNode = tempNode.getNext();

        }
        return preNode;
    }

    public void clear(){
        MyListNode preNode = head;
        MyListNode tempNode;

        if (head.getNext() == null){
            return ;
        }
        for (int i = 0; i < count-1; i++){
            tempNode = preNode.getNext();
            preNode.setNext(null);
            preNode = tempNode;
        }
    }

    public void printAll(){
        MyListNode tempNode = head;

        for (int i = 0; i< count ; i++){
            System.out.println("position : "+i+" -> "+tempNode.getData());
            tempNode = tempNode.getNext();
        }
    }

    public int getCount() {
        return count;
    }
}

 

 

3. Test

---

• 독립적인 test를 위해 매 번 test실행 전 5개만 순서대로 저장, test 후 claer 해줌.
• clear는 연결 관계를 null로 변경함.

class MyLinkedListTest {

    MyLinkedList myLinkedList = new MyLinkedList();
    int cnt = 5;

    @BeforeEach
    void initTest(){

        for (int i=0; i<5; i++){
            myLinkedList.addElement(Integer.toString(i));
        }
        myLinkedList.printAll();
    }

    @AfterEach
    void afterTest(){
        myLinkedList.clear();
    }

    @Test
    void addElement() {
        myLinkedList.addElement("A");
        String element = myLinkedList.getElement(cnt);
        assertEquals(element, "A");
    }

    @Test
    void insertElement() {
        int insertPosition = 2;

        myLinkedList.insertElement(insertPosition, "A");
        String element = myLinkedList.getElement(insertPosition);
        assertEquals(element, "A");
    }

    @Test
    void insertElementPositionZero(){
        int insertPosition = 0;

        myLinkedList.insertElement(insertPosition, "A");
        String element = myLinkedList.getElement(insertPosition);
        assertEquals(element, "A");
    }

    @Test
    void insertElementWrongPosition(){
        int insertPosition = myLinkedList.getCount() + 10;

        assertThrows(IllegalArgumentException.class, ()-> myLinkedList.insertElement(insertPosition, "A"));
    }

    @Test
    void removeElement() {

        int deletePosition = 2;
        String next = myLinkedList.getElement(deletePosition+1);

        myLinkedList.removeElement(deletePosition);

        int count = myLinkedList.getCount();
        System.out.println("count = " + count);

        myLinkedList.printAll();
        assertEquals(count, cnt-1);
        assertEquals(myLinkedList.getElement(deletePosition), next);
    }

    @Test
    void removeElementWrongPosition(){
        int removePosition = myLinkedList.getCount() + 10;

        assertThrows(IllegalArgumentException.class, ()-> myLinkedList.removeElement(removePosition));
    }

    @Test
    void clearTest(){
        myLinkedList.clear();
        MyListNode head = myLinkedList.getNode(0);

        assertNull(head.getNext());
    }


}

 

4. GitHub: 211024 LinkedList 구현

---

GitHub - bsh6463/dataStructure