[JAVA/자료구조] 강의노트 3강 下 : Linkedlist/NodeList(노드리스트, 단방향 연결리스트) 구현, 코드

---

저번 시간에는 ArrayList를 공부해보았습니다.

이어서 NodeList를 공부해보겠습니다.

 

1) 연결리스트(LinkedList)

LinkedList는 Node를 이용한 배열구조입니다.

ArrayList와 마찬가지로 2강에서 Stack과 Queue를 공부하면서 맛보기로 살펴본적이 있습니다.

먼저 연결리스트에서 node의 정의에 대해 알아보겠습니다

노드(node) : 연결 리스트에서 데이터가 저장되는 실제 노드(공간)

고로 nodelist는 데이터가 저장되는 공간의 리스트라고 이해하쉬면 쉬울 것 같습니다.

그리고 그 리스트의 처음을 head node, 끝을 tail node라고 부릅니다.

 

2) LinkedList Operation

- Node first() : 첫 번째 노드의 값을 불러옵니다.

- Node Last() : 마지막 노드의 값을 불러옵니다.

- Node prev(Node p) : p번째 노드의 전 노드의 값을 불러옵니다.

- Node next(Node p) : p번째 노드의 다음 노드의 값을 불러옵니다.

- set(Node p, object e) : p번째 노드의 값을 e로 바꿉니다.

- addBefore(Node p, object e) : p번째 노드의 전에 e값을 가진 노드를 추가합니다.

- addAfter(Node p, object e) : p번째 노드의 다음에 e값을 가진 노드를 추가합니다.

- addFirst(object e) : 첫 번째 위치에 e값을 가진 노드를 추가합니다.

- addLast(object e) : 마지막 위치에 e값을 가진 노드를 추가합니다.

- object remove(Node p) : p번째 노드를 제거합니다.

---

!) LinkedList Operation Example

Operation	Output	In_NodeList
addFirst(8)	-	(8)
addAfter(p1, 5)	-	(8, 5)
addLast(3)	-	(8, 5, 3)
Node first()	8	(8, 5, 3)
object remove(p3)	3	(8, 5)
Node last()	5	(8, 5)
set(p2, 7)	5	(8, 7)
Node prev(p2)	8	(8, 7)
addBefore(p2, 6)	-	(8, 6, 7)
Node next(p1)	6	(8, 6, 7)

---

 

3) LinkedList 구현

class LinkedList{
    private static Node head;
    private static int numNodes;
    
    
    public LinkedList(Object e)
    {
        head = new Node(e);
    }
    
    public void addAtHead(Object e)
    {
        Node temp = head;
        head = new Node(e);
        head.next = temp;
        numNodes++;
    }
    
    public void addAtTail(Object e)
    {
        Node temp = head;
        while(temp.next != null)
        {
            temp = temp.next;
        }
        
        temp.next = new Node(e);
        numNodes++;
    }
    
    public void addAtIndex(int index, Object e)
    {
        Node temp = head;
        Node holder;
        for(int i=0; i < index-1 && temp.next != null; i++)
        {
            temp = temp.next;
        }
        holder = temp.next;
        temp.next = new Node(e);
        temp.next.next = holder;
        numNodes++;
    }
    
    public void deleteAtIndex(int index)
    {
        Node temp = head;
        for(int i=0; i< index - 1 && temp.next != null; i++)
        {
            temp = temp.next;
        }
        temp.next = temp.next.next;
        numNodes--;
    }
}
    

이번 코드는 직접 만든 것이 아니라 github의 글을 가져왔습니다.

제가 만든 코드와 비교해볼 때 훨씬 완성도가 높은 것 같아 다른 글을 참조하여 소개해드립니다.

더 열심히 학습하여 제 코드로만 블로그를 포스팅 할 수 있도록 노력해야겠습니다..

원본 글 보러가기

A linked list class implemented in Java

다음 시간엔 tree에 대해서 공부해보겠습니다.

감사합니다 :)