您好,登錄后才能下訂單哦!
這篇文章主要介紹了Java數(shù)據(jù)結(jié)構(gòu)之鏈表的相關(guān)知識(shí)有哪些,具有一定借鑒價(jià)值,感興趣的朋友可以參考下,希望大家閱讀完這篇文章之后大有收獲,下面讓小編帶著大家一起了解一下。
鏈表是真正動(dòng)態(tài)的數(shù)據(jù)結(jié)構(gòu),最簡(jiǎn)單的動(dòng)態(tài)數(shù)據(jù)結(jié)構(gòu),基本用于輔助組成其他數(shù)據(jù)結(jié)構(gòu)。
數(shù)據(jù)存儲(chǔ)在“節(jié)點(diǎn)”(Node)中
優(yōu)點(diǎn):真正的動(dòng)態(tài),不需要處理固定容量的問(wèn)題
缺點(diǎn):?jiǎn)适Я穗S機(jī)訪問(wèn)的能力
定義Node節(jié)點(diǎn)
private class Node{ public E e; public Node next; public Node(E e, Node next){ this.e = e; this.next = next; } public Node(E e){ this(e, null); } public Node(){ this(null,null); } @Override public String toString() { return e.toString(); } }
向鏈表中添加元素
具體代碼實(shí)現(xiàn):
//向鏈表中間添加元素 //在鏈表的index(0-based)位置添加新的元素e public void add(int index, E e){ if(index < 0 || index > size) throw new IllegalArgumentException("Add failed.Illeagl failed."); Node prev = dummyHead; for (int i = 0; i < index; i++) { prev = prev.next; } // Node node = new Node(e); // node.next = prev.next; // prev.next = node; prev.next = new Node(e, prev.next); size++; }
向鏈表中刪除元素
具體代碼實(shí)現(xiàn):
//鏈表中刪除index(0-based)位置的元素,返回刪除的元素 public E remove(int index){ if(index < 0 || index >= size) throw new IllegalArgumentException("Remove failed.Illeagl failed."); Node pre = dummyHead; for (int i = 0; i < index; i++) { pre = pre.next; } Node retNode = pre.next; pre.next = retNode.next; retNode.next = null; size--; return retNode.e; }
鏈表功能的實(shí)現(xiàn)及測(cè)試類
public class LinkedList<E> { private class Node{ public E e; public Node next; public Node(E e, Node next){ this.e = e; this.next = next; } public Node(E e){ this(e, null); } public Node(){ this(null,null); } @Override public String toString() { return e.toString(); } } private Node dummyHead; private int size; public LinkedList(){ dummyHead = new Node(null, null); size = 0; } //獲取鏈表中的元素個(gè)數(shù) public int getSize(){ return size; } //返回鏈表是否為空 public boolean isEmpty(){ return size == 0; } //向鏈表頭添加元素 public void addFirst(E e){ // Node node = new Node(e); // node.next = head; // head = node; add(0, e); } //向鏈表中間添加元素 //在鏈表的index(0-based)位置添加新的元素e public void add(int index, E e){ if(index < 0 || index > size) throw new IllegalArgumentException("Add failed.Illeagl failed."); Node prev = dummyHead; for (int i = 0; i < index; i++) { prev = prev.next; } // Node node = new Node(e); // node.next = prev.next; // prev.next = node; prev.next = new Node(e, prev.next); size++; } //在鏈表的末尾添加新的元素e public void addLast(E e){ add(size, e); } //獲得鏈表的第index(0-based)個(gè)位置的元素 //在鏈表中不是一個(gè)常用的操作 public E get(int index){ if(index < 0 || index > size) throw new IllegalArgumentException("Add failed.Illeagl failed."); Node cur = dummyHead.next; for (int i = 0; i < index; i++) { cur = cur.next; } return cur.e; } //獲得鏈表的第一個(gè)元素 public E getFirst(){ return get(0); } //獲得鏈表的最后一個(gè)元素 public E getLast(){ return get(size - 1); } //修改鏈表的第index(0-based)個(gè)位置的元素 //在鏈表中不是一個(gè)常用的操作 public void set(int index, E e){ if(index < 0 || index > size) throw new IllegalArgumentException("Add failed.Illeagl failed."); Node cur = dummyHead.next; for (int i = 0; i < index; i++) { cur = cur.next; } cur.e = e; } //查找鏈表中是否有元素e public boolean contains(E e){ Node cur = dummyHead.next; while(cur != null){ if(cur.e.equals(e)){ return true; } cur = cur.next; } return false; } //鏈表中刪除index(0-based)位置的元素,返回刪除的元素 public E remove(int index){ if(index < 0 || index >= size) throw new IllegalArgumentException("Remove failed.Illeagl failed."); Node pre = dummyHead; for (int i = 0; i < index; i++) { pre = pre.next; } Node retNode = pre.next; pre.next = retNode.next; retNode.next = null; size--; return retNode.e; } //從鏈表中刪除第一個(gè)元素 public E removeFirst(){ return remove(0); } //從鏈表中刪除最后一個(gè)元素 public E removeLast(){ return remove(size - 1); } @Override public String toString() { StringBuilder res = new StringBuilder(); // Node cur = dummyHead.next; // while (cur != null){ // res.append(cur + "->"); // cur = cur.next; // } for (Node cur = dummyHead.next; cur != null; cur = cur.next){ res.append(cur + "->"); } res.append("null"); return res.toString(); } public static void main(String[] args) { LinkedList<Integer> linkedList = new LinkedList<>(); for (int i = 0; i < 5; i++) { linkedList.addFirst(i); System.out.println(linkedList); } linkedList.add(2, 666); System.out.println(linkedList); linkedList.remove(2); System.out.println(linkedList); linkedList.removeFirst(); System.out.println(linkedList); linkedList.removeLast(); System.out.println(linkedList); } }
使用第二章中的棧接口,創(chuàng)建第一節(jié)中的鏈表實(shí)現(xiàn)對(duì)象,實(shí)現(xiàn)棧的操作,具體如下:
public class LinkedListStack<E> implements Stack<E> { private LinkedList<E> list; public LinkedListStack(){ list = new LinkedList<>(); } @Override public int getSize() { return list.getSize(); } @Override public boolean isEmpty() { return list.isEmpty(); } @Override public void push(E value) { list.addFirst(value); } @Override public E pop() { return list.removeFirst(); } @Override public E peek() { return list.getFirst(); } @Override public String toString() { StringBuilder res = new StringBuilder(); res.append("Stack : top"); res.append(list); return res.toString(); } public static void main(String[] args) { LinkedListStack<Integer> stack = new LinkedListStack<>(); for (int i = 0; i < 5; i++) { stack.push(i); System.out.println(stack); } stack.pop(); System.out.println(stack); } }
使用第二章中的隊(duì)列接口,創(chuàng)建無(wú)頭節(jié)點(diǎn)的鏈表實(shí)現(xiàn)隊(duì)列操作,具體如下:
public class LinkedListQueue<E> implements Queue<E> { private class Node{ public E e; public LinkedListQueue.Node next; public Node(E e, LinkedListQueue.Node next){ this.e = e; this.next = next; } public Node(E e){ this(e, null); } public Node(){ this(null,null); } @Override public String toString() { return e.toString(); } } private Node head,tail; private int size; public LinkedListQueue(){ head = null; tail = null; size = 0; } @Override public int getSize() { return size; } @Override public boolean isEmpty() { return size == 0; } @Override public void enqueue(E e) { if(tail == null){ tail = new Node(e); head = tail; }else{ tail.next = new Node(e); tail = tail.next; } size++; } @Override public E dequeue() { if (isEmpty()) throw new IllegalArgumentException("Cannot dequeue form any empty queue."); Node retNode = head; head = head.next; retNode.next = null; if (head == null) tail = null; return retNode.e; } @Override public E getFront() { if (isEmpty()) throw new IllegalArgumentException("Cannot getFront form any empty queue."); return head.e; } @Override public String toString() { StringBuilder res = new StringBuilder(); res.append("Queue : front "); Node cur = head; while (cur != null){ res.append(cur + "->"); cur = cur.next; } res.append("Null tail"); return res.toString(); } public static void main(String[] args) { LinkedListQueue<Integer> queue = new LinkedListQueue<>(); for (int i = 0; i < 10; i++) { queue.enqueue(i); System.out.println(queue); if(i % 3 == 2){ queue.dequeue(); System.out.println(queue); } } } }
感謝你能夠認(rèn)真閱讀完這篇文章,希望小編分享的“Java數(shù)據(jù)結(jié)構(gòu)之鏈表的相關(guān)知識(shí)有哪些”這篇文章對(duì)大家有幫助,同時(shí)也希望大家多多支持億速云,關(guān)注億速云行業(yè)資訊頻道,更多相關(guān)知識(shí)等著你來(lái)學(xué)習(xí)!
免責(zé)聲明:本站發(fā)布的內(nèi)容(圖片、視頻和文字)以原創(chuàng)、轉(zhuǎn)載和分享為主,文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng),如果涉及侵權(quán)請(qǐng)聯(lián)系站長(zhǎng)郵箱:is@yisu.com進(jìn)行舉報(bào),并提供相關(guān)證據(jù),一經(jīng)查實(shí),將立刻刪除涉嫌侵權(quán)內(nèi)容。