鍊錶也是線性的資料結構,與陣列不同的是,鍊錶在記憶體中的儲存方式是隨機儲存。
下面給出涵蓋鍊錶四個操作的一個完整的例子,有幾點需要注意的是:
(一)在增刪改查之前,都需要對給出的下標進行邊界判斷;
(二)增加一個名為last的節點,可以方便在鍊錶的尾部進行操作,省去了查找到最後一個節點的時間複雜度;
# (三)在鍊錶的內部插入元素時,我們先找到要插入位置的前一個節點prevNode,然後可以記錄下prevNode的next,插入時先將prevNode的next指向要插入的節點,再將要插入的節點的next指向目前的next。這點和C 中的操作也略有不同;
(四)刪除節點時,用removedNode來記錄刪除節點的回傳值,並且不要忘了size要減1。
相關免費影片教學推薦:java免費影片教學
操作範例如下:
public class MyLinkedList { //定义一个静态的内部类 private static class Node{ int data; Node next; Node(int data){ this.data = data; } } private Node head; private Node last;//为了方便尾部插入元素的操作 private int size;//size表示链表的实际长度 public void insert(int data, int index)throws Exception{ if(index < 0 || index > size) throw new IndexOutOfBoundsException("超出链表节点范围!"); Node insertedNode = new Node(data); if(size == 0){//插入第一个元素时元素个数为0 head = insertedNode; last = insertedNode; }else if(size == index){//在链表的末尾插入 last.next = insertedNode; last = insertedNode; }else{ Node prevNode = get(index - 1); Node nextNode = prevNode.next; prevNode.next = insertedNode; insertedNode.next = nextNode; } size++; } public void update(int data, int index) throws Exception{ if(index < 0 || index >= size) throw new IndexOutOfBoundsException("超出链表节点范围!"); if(index == 0) head.data = data; else if(index == size - 1) last.data = data; else{ Node temp = get(index); temp.data = data; } } public Node remove(int index) throws Exception { if(index < 0 || index >= size){ throw new IndexOutOfBoundsException("超出链表节点范围!"); } Node removedNode = null;//不给removedNode分配堆内存 if(index == 0){ removedNode = head; head = head.next; } else if(index == size - 1){ //删除尾结点 Node prevNode = get(index - 1); removedNode = prevNode.next; prevNode.next = null; last = prevNode; } else{ Node prevNode = get(index - 1); Node nextNode = prevNode.next.next; removedNode = prevNode.next; prevNode.next = nextNode; } size--; return removedNode; } //查找链表元素 public Node get(int index) throws Exception{ if(index < 0 || index >= size){ throw new IndexOutOfBoundsException("超出链表节点范围!"); } Node temp = head; for(int i = 0; i < index; i++){ temp = temp.next; } // size--; return temp; } //输出链表 public void output(){ Node temp = head; while(temp != null){ System.out.println(temp.data); temp = temp.next; } } public static void main(String[] args) throws Exception{ MyLinkedList myLinkedList = new MyLinkedList(); myLinkedList.insert(3,0); myLinkedList.insert(7,1); myLinkedList.insert(9,2); myLinkedList.insert(5,3); myLinkedList.insert(6,1); myLinkedList.remove(0); myLinkedList.update(2,1); myLinkedList.output(); System.out.println(myLinkedList.size); } }
想了解更多相關教學可以存取:java開發入門
以上是如何實現java鍊錶中的基本操作(增、刪、查、改)的詳細內容。更多資訊請關注PHP中文網其他相關文章!