Java中常用的數據結構有許多種,其中順序表和鏈表就是兩種常見的數據結構。
順序表是一種線性數據結構,采用一段連續的內存空間存儲數據。我們可以用數組實現一個順序表。順序表的插入、刪除操作是比較耗時的,時間復雜度為O(n)。
/** * 順序表的實現 */ public class SeqList<T> { private Object[] data; private int size; private int capacity; public SeqList(int capacity) { this.capacity = capacity; this.data = new Object[capacity]; this.size = 0; } public void add(T element) { if (size == capacity) { throw new RuntimeException("SeqList is full!"); } data[size++] = element; } public T get(int index) { if (index < 0 || index >= size) { throw new IndexOutOfBoundsException("Index out of bounds!"); } return (T) data[index]; } }
鏈表是另一種線性數據結構,不同于順序表,它采用一組任意的存儲單元存儲數據,存儲單元間存在指針指向下一個存儲單元。鏈表插入、刪除操作比較快,只需要改變節點的指針,時間復雜度為O(1)。
/** * 鏈表的實現 */ public class LinkedList<T> { private Node head; private int size; private class Node { T data; Node next; Node(T data) { this.data = data; this.next = null; } } public LinkedList() { this.head = null; this.size = 0; } public void add(T element) { Node newNode = new Node(element); if (head == null) { head = newNode; } else { Node p = head; while (p.next != null) { p = p.next; } p.next = newNode; } size++; } public T get(int index) { if (index < 0 || index >= size) { throw new IndexOutOfBoundsException("Index out of bounds!"); } Node p = head; for (int i = 0; i < index; i++) { p = p.next; } return p.data; } }
在實際開發中,我們需要結合具體業務場景選擇不同的數據結構。如果我們需要頻繁進行插入和刪除操作,可以考慮使用鏈表;如果我們頻繁進行查找操作,可以考慮使用順序表。
上一篇div(rotA)=0
下一篇div。this