1.概念的引入
相信大家都使用過各種集合來進行開發,但是較少的人會去研究其內部的存儲原理和調用方法,今天我就來帶大家一起學習數據結構算法:雙向鏈表
首先我們先來了解什麼是緩存,以及數據在內存中的存儲方式.
1.緩存是什麼
如果cup讀取數據時,每次讀取都是從內存再到硬盤讀取,那麼效率就太低了.
所以可以預先把數據存到內存,然後cup下次從內存讀取即可.
2.數據在內存中的存儲方式
第1種.線性
所謂線性,就是內存是連續的
舉例ArrayList或者數組:我們知道,數組存儲數據的時候,當你申請100個大小,但是內存不足的時候就會導致內存不足而失敗,或者即使你請求到了100個,但是你只存3個數據,那麼就浪費內存了
=>優點:查找數據快(好比幾個好朋友乘火車,車票都連在一起就好找了)
缺點:1,內存不足就失敗;2.浪費內存(買了10張火車票,但是隻有3個人乘車,那麼就浪費了7張)
第2種.鏈接
內存是鏈接的(用於解決內存不足,解決線性(上面)問題的不足),比如不連續的空間也能存數據,比如買火車票,有火車票就賣給你,要幾張賣幾張,不連續位置的也賣.
=>優點:解決內存不足,解決內存浪費
缺點:找人比較慢(票不連續,不一定在一個車廂)
節點的屬性:
多個節點的內部構造:
代碼思路
一.添加節點add(Object obj)
1.Node節點屬性:
prev:存放前節點(相當於地址,地址就是指針,指針就是地址)
data:Object各種數據
next:存放下節點
2.定義head,rear節點,當只有一個節點,那麼head和rear同指一個節點
3.節點添加的方法add(Object obj)
1.創建節點new Node(),即每加一個數據就創一個節點
2.放數據
3.把節點放入鏈表中
1.如果頭結點為空,那麼頭結點和尾節點都指向該節點
2.如果頭節點不為空
1.往尾部添加
原來的next指向新節點
rear.next = note;
新節點pre指向原節點,新節點也變成尾節點
note.pre = rear
(ps,有需求再設置往頭部添加)
4.toString方法[元素1,元素2,元素3] while(head!=null) if(head!=rear)append(head.data+","),***同temp代替head,否則會破壞head,影響後面的remove時head變才null了
添加節點過程圖
二.刪除節點數據remove(Object obj)
注意判斷該節點:1.是head 2.還是 rear 3.還是中間某值
1.查找數據所在節點find(Object obj)
1.從頭結點開始遍歷Note temp = head
2.while循環(temp!=null) 如果找到是數據相同就停止
判斷數據相同的兩標準 equals 和hashCode()
否則temp = temp.next,下一個
3.返回節點
2. 確實找到一個有該數據的節點if(delete!=null),然後有4種情況如果刪的是以下的
1.只有一個節點->既是頭又是尾=>頭尾都設空
2.是頭結點=>新節點變頭節點,新節點的pre變null
3.是尾節點=>新節點變尾節點,新節點的next變null
4.是其他
=>前一個節點的next=該節點的next
後一個節點的pre = 該節點的pre;
刪除節點過程圖
三.修改數據update(Object oldData,Object newData)
1.找到data所在的節點find(oldData);
2.如果找到的節點不為空,就把data變成newData.
四.容器中是否包含數據contains(Object data)
1.同理根據find(data)
2.返回 !note==null即可,不為空就是有包含
五.可以改成增強泛型版,把所有的Object改成T,就可以增強為選擇和泛型非泛型了
雙向鏈表的迭代器
直接增強for循環或者迭代就報錯,因為沒實現接口iterable,該接口是所有集合的頂級接口.
1.實現iterable
2.重寫iterator方法
1.返回new Iterator()
1.hasNext()方法
返回是否有數據 Note temp = head
temp==null;
2.next()方法
1.返回temp.data
2.temp指向下一個.temp = temp.next
3.remove()方法-不改變
3.ArrayList不給在增強for循環或者迭代器中做增刪改,所以自己也可用設置,根據ArrayList的設計方法,同理,設置一個變量modCount.
1.在自己的鏈表類成員變量定義
2.在增刪改的時候++;
3.在迭代器裡面設置一個標記=modCount.(此時和前面的鏈表操作後的情況值的大小相同);
4.迭代過程中,如果再做了增刪改的操作,就拋出異常.
寫在next()方法的首位,if(標記改變),也拋出concurrentMotificationExaption(不能做增刪改)
初學者有什麼不懂的可以私信我，需要系統學習資料和系統學習框架圖的同學，可關注小編頭條號，歡迎留言評論和私信小編。【私信方法】文章上方處點擊“作者頭像”，進入作者首頁，在作者主頁上方點擊“關注”旁邊的“發私信”即可。私信內容：學習幫助。
閱讀更多 岑寂扶你去學C 的文章
