[Study] 2017-04-09 링크드리스트

etc/study 2017. 4. 9. 11:58

2017-04-09 링크드 리스트

1. Javascript

<!DOCTYPE html> <head> <meta charset="UTF-8"> <title>Title</title> </head> <script> //element: data, next: nextnode function Node(element){ this.element = element; this.next = null; } //초기 head.next는 null function LList(){ this.head = new Node("head"); this.find = find; this.insert = insert; this.remove = remove; this.display = display; this.findPrevious = findPrevious; } function find(item){ var currNode = this.head; while(currNode.element != item){ currNode = currNode.next; } return currNode; } function insert(newElement, item){ var newNode = new Node(newElement); var current = this.find(item); newNode.next = current.next; current.next = newNode; } function display(){ var currNode = this.head; while(!(currNode.next==null)){ console.log(currNode.next.element); currNode = currNode.next; } } function findPrevious(item){ var currNode = this.head; while(!(currNode.next == null) && (currNode.next.element != item)){ currNode = currNode.next; } return currNode; } function remove(item){ var prevNode = this.findPrevious(item); if(!(prevNode.next == null)){ prevNode.next = prevNode.next.next; } } var cities = new LList(); cities.insert("Conway","head"); cities.insert("Seoul","Conway"); cities.display(); </script> </text>

2. Java

- 링크드 리스트는 데이터 추가 삭제시에 효율적이다

- 메모리가 허용되는 한 계속 추가 할 수 있다

1. Node<T>.class

class Node<T> { private Node<T> nextRef; private T value; public void setValue(T value){ this.value = value; } public T getValue(){ return value; } public void setNextRef(Node<T> nextRef){ this.nextRef = nextRef; } public Node<T> getNextRef(){ return nextRef; } }

- 위에 있는 data/next의 한 블록을 노드라고 한다

- 링크드 리스트를 구현하기 위해선 노드가 필요하다

- data는 노드의 값이면 next는 다음 노드를 가르키기 위한 주소 값이 들어간다

2. SingleLinkedList<T>.class

1) 변수 정의

private Node<T> head; private Node<T> tail; private int size = 0;

- head, tail 객체를 선언한다. head와 tail은 노드의 추가 삭제시의 참고가 된다

- head, tail은 하나의 노드라기 보다는 노드들을 컨트롤 할 수 있는 설명서의 역할

- size는 엘리먼트의 크기를 나타 낸다

2) addLast(T element)

public void addLast(T element){ Node<T> newNode = new Node<T>(); newNode.setValue(element); System.out.println("adding:"+element); size++; if(head == null){ head = newNode; tail = newNode; }else{ //이 부분은 결국 앞 노드의 다음 노드를 가르키는 부분을 셋팅 하는 것과 같다 tail.setNextRef(newNode); tail = newNode; } }

- 노드를 뒤에서 추가한다

- 노드가 없을 시에 처음 head와 tail은 모두 처음 추가된 노드를 가르키게 된다

- 이후에 추가된 노드는 tail 값을 참조하여 추가한다

- 처음 추가된 노드가 얕은 복사(shallow copy) 과정이 일어나서 tail의 next값을 셋팅 하더라도 앞 노드의 다음 주소값을 셋팅 하는 효과가 일어난다

3) addFirst(T element)

public void addFirst(T element){ Node<T> newNode = new Node<>(); newNode.setValue(element); newNode.setNextRef(head); head = newNode; size++; //처음 노드 일 때 if(head.getNextRef() == null){ tail = newNode; } }

- head의 값을 참조 하여 앞에 노드를 추가한다

- 처음 노드가 추가 되는 거라면 tail을 새로운 노드로 지정

4) node(int x)

public Node<T> node(int x){ Node<T> temp = head; //인덱스 값을 바탕으로 탐색을 시작 for(int i = 0; i<x; i++){ temp = temp.getNextRef(); } return temp; }

- 특정 노드의 위치를 찾는 함수이다

- 이 함수를 이용하여 특정위치 추가/삭제 또는 데이터 가져오기가 가능하다

- head를 시작으로 계속 다음 노드 값을 추적하여 최종 인덱스 의 값을 찾는다

5) add(T element, int x)

public void add(T element,int index){ Node<T> newNode = new Node<>(); newNode.setValue(element); if(size == index + 1){ addLast(element); }else if(index == 0){ addFirst(element); }else{ Node<T> temp = node(index-1); newNode.setNextRef(temp.getNextRef()); temp.setNextRef(newNode); size++; if(newNode.getNextRef() == null){ tail = newNode; } } }

- 특정 위치에 노드를 삽입한다

- index - 1은 원하는 위치의 값은 바로 그 뒤의 노드가 알기 때문에 바로뒤의 노드를 이용하여 삽입한다

6) deleteFirst()

public Node<T> deleteFirst(){ Node<T> returnData = head; head = returnData.getNextRef(); System.out.println("deleteFirst:"+returnData.getValue()); size--; return returnData; }

- 앞의 노드 삭제

- head를 앞의 노드가 가르키는 값으로 지정한다

7) delete(int T)

public Node<T> delete(int element){ if(element == 0){ return deleteFirst(); } Node<T> temp = node(element-1); Node<T> deletedData = temp.getNextRef(); temp.setNextRef(temp.getNextRef().getNextRef()); size--; if(deletedData == tail){ tail = temp; } System.out.println("delete:" +deletedData.getValue()); return deletedData; }

- 특정 위치의 노드를 삭제한다

- node()를 이용하여 위치를 찾고 사이의 연결 고리를 이어준다

8) deleteLast()

public Node<T> deleteLast(){ return delete(size-1); }

- 마지막 노드 삭제

9) toString()

public String toString(){ if(head == null){ return "[]"; } Node<T> temp = head; String str = "["; while(temp.getNextRef() != null){ str += temp.getValue() + ","; temp = temp.getNextRef(); } str += temp.getValue(); return str+"]"; }

- 요소의 상태를 알 수 있도록 화면에 출력한다

10) get()

public T get(int x){ Node<T> temp = node(x); return temp.getValue(); }

- 요소 값 가져오기

11) main()

public static void main(String[]args){ SingleLinkedList<Integer> node = new SingleLinkedList(); node.addLast(1); System.out.println(node); node.addLast(2); System.out.println(node); node.addLast(3); System.out.println(node); node.addFirst(9); System.out.println(node); node.addFirst(10); System.out.println(node); node.deleteLast(); System.out.println(node); node.deleteLast(); System.out.println(node); node.add(99, 1); System.out.println(node); node.add(100, 3); System.out.println(node); node.add(1000, 0); System.out.println(node); System.out.println(node.get(2)); }

'etc > study' 카테고리의 다른 글

960 그리드 시스템 (0)	2018.02.19
자바스크립트 클릭이벤트 click() (0)	2018.02.09
요소 가운데 정렬 (0)	2018.02.02
[study] 2017-04-16 더블링크드리스트 (0)	2017.04.16

리딩리드

일	월	화	수	목	금	토
			1	2	3	4
5	6	7	8	9	10	11
12	13	14	15	16	17	18
19	20	21	22	23	24	25
26	27	28	29	30	31