연결 자료구조 | Linked List | 連結リスト（2）

단순 연결 리스트

단순 연결 리스트에서의 삽입 연산

1. 삽입할 새 노드를 메모리에서 가져와서 포인터 변수 new가 가리키게 한다.
2. 새로운 데이터 필드에는 삽입할 값을 저장한다.
3. 전 노드의 주소값을 new의 주소에 저장한다.
4. 전 노드 주소값에 new의 주소값을 저장한다.

🥕중간에 삽입하기

// x가 index 다음에 삽입되도록
// 예시 ) 숫자 3이 2번 인덱스의 노드 이후에 연결되도록
void pushMiddle(int x,int index){
            Node newNode = new Node(x);
            Node temp =this;
            int count = 0;
            while(temp.next!=null) {
                temp = temp.next;
                count++;
                if (count == index) {
                    break;
                }
            }
            Node temp2=temp.next;
            temp.next=newNode;
            newNode.next=temp2;
        }

🥕마지막에 삽입하기

void insert(int x){
            Node newNode = new Node(x);
            Node temp = this;
            while(temp.next!=null){
                temp=temp.next;
            }
            temp.next=newNode;
        }

단순 연결 리스트에서의 삭제 연산

1. 삭제할 노드의 앞 노드를 찾는다.
2. 앞 노드의 주소에 삭제할 노드의 주소를 저장한다.

🥕특정 원소 삭제

void delete(int x){
            Node temp = this;
            while(temp.next!=null){
                if(temp.next.data==x){
                    temp.next=temp.next.next;
                }else{
                    temp=temp.next;
                }
            }
        }

단순 연결 리스트에서의 노드 탐색 알고리즘

1. 시작 주소를 노드 탐색을 위해 사용할 순회 포인터 temp의 시작 위치로 지정한다.
2. temp가 null이 아닐 동안,temp의 데이터값이 x인지를 검사하여 x이면 그 노드의 주소를 반환하고, x가 아니면 다음 노드로 포인터를 이동시킨다.
3. x노드를 찾지 못한 경우 null 값을 가진 포인터를 반환한다.

좀 다르게 구현하긴 했는데 뭐..

Boolean search(int x){
            Node temp = this;
            while(temp.next!=null){
                if(temp.next.data==x){
                    return true;
                }else{
                    temp=temp.next;
                }
            }
            return false;
        }

---

JAVA 전체코드

public class Main {
    static class Node{
        int data;
        Node next=null;

        Node(int x){
            this.data=x;
        }

        void pushMiddle(int x,int index){
            Node newNode = new Node(x);
            Node temp =this;
            int count = 0;
            while(temp.next!=null) {
                temp = temp.next;
                count++;
                if (count == index) {
                    break;
                }
            }
            Node temp2=temp.next;
            temp.next=newNode;
            newNode.next=temp2;
        }

        void push(int x){
            Node newNode = new Node(x);
            Node temp = this;
            while(temp.next!=null){
                temp=temp.next;
            }
            temp.next=newNode;
        }
        void delete(int x){
            Node temp = this;
            while(temp.next!=null){
                if(temp.next.data==x){
                    temp.next=temp.next.next;
                }else{
                    temp=temp.next;
                }
            }
        }

        Boolean search(int x){
            Node temp = this;
            while(temp.next!=null){
                if(temp.next.data==x){
                    return true;
                }else{
                    temp=temp.next;
                }
            }
            return false;
        }
        void print(){
            Node point = this;
            while(point.next!=null){
                System.out.print(point.data+"=>");
                point=point.next;
            }
            System.out.println(point.data);
        }
    }
    public static void main(String[] args){
        Node head = new Node(1);
        head.push(10);
        head.push(73);
        head.push(8);
        head.push(11);
        System.out.println(head.search(7));
        head.pushMiddle(99,3);
        head.print();
    }
}