Java數據結構之鏈表相關知識總結
一、鏈表
1.1 概述
鏈表是真正動態的數據結構,最簡單的動態數據結構,基本用於輔助組成其他數據結構。
數據存儲在“節點”(Node)中
優點:真正的動態,不需要處理固定容量的問題
缺點:喪失瞭隨機訪問的能力
1.2 鏈表使用的基本功能
定義Node節點
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(); } }
向鏈表中添加元素
具體代碼實現:
//向鏈表中間添加元素 //在鏈表的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++; }
向鏈表中刪除元素
具體代碼實現:
//鏈表中刪除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; }
鏈表功能的實現及測試類
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; } //獲取鏈表中的元素個數 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)個位置的元素 //在鏈表中不是一個常用的操作 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; } //獲得鏈表的第一個元素 public E getFirst(){ return get(0); } //獲得鏈表的最後一個元素 public E getLast(){ return get(size - 1); } //修改鏈表的第index(0-based)個位置的元素 //在鏈表中不是一個常用的操作 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; } //從鏈表中刪除第一個元素 public E removeFirst(){ return remove(0); } //從鏈表中刪除最後一個元素 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); } }
二、鏈表實現棧操作
使用第二章中的棧接口,創建第一節中的鏈表實現對象,實現棧的操作,具體如下:
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); } }
三、鏈表實現隊列操作
使用第二章中的隊列接口,創建無頭節點的鏈表實現隊列操作,具體如下:
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); } } } }
到此這篇關於Java數據結構之鏈表相關知識總結的文章就介紹到這瞭,更多相關Java鏈表內容請搜索WalkonNet以前的文章或繼續瀏覽下面的相關文章希望大傢以後多多支持WalkonNet!