目錄
鏈表和LinkedList
?1.鏈表的實(shí)現(xiàn)
2.LinkedList的使用
3.ArrayList和LinkedList的區(qū)別
4.鏈表OJ題訓(xùn)練
鏈表和LinkedList
? ? ? ? 當(dāng) 在 ArrayList 任意位置插入或者刪除元素時(shí)，就需要將后序元素整體往前或者往后搬移，時(shí)間復(fù)雜度為 O(n) ，效率比較低，因此 ArrayList 不適合做任意位置插入和刪除比較多的場(chǎng)景。鏈表是一種 物理存儲(chǔ)結(jié)構(gòu)上非連續(xù) 存儲(chǔ)結(jié)構(gòu)，數(shù)據(jù)元素的 邏輯順序 是通過(guò)鏈表中的 引用鏈接 次序?qū)崿F(xiàn)的 。
?1.鏈表的實(shí)現(xiàn)
鏈表結(jié)構(gòu)有三種情況，可以相互組合共八種鏈表結(jié)構(gòu)。
- 單向或雙向
- 帶頭或不帶頭（頭結(jié)點(diǎn)一般裝鏈表長(zhǎng)度信息）
- 循環(huán)或非循環(huán)
下面是無(wú)頭單向非循環(huán)鏈表的實(shí)現(xiàn)：
public class MyLinkedList {
class LinkedNode{
int val;
LinkedNode next;
public LinkedNode(int val){
this.val=val;
}
}
LinkedNode head;
// 1、無(wú)頭單向非循環(huán)鏈表實(shí)現(xiàn)
//頭插法
public void addFirst(int data){
if(head==null){
head.val=data;
}else{
LinkedNode node=new LinkedNode(data);
node.next=head;
head=node;
}
}
//尾插法
public void addLast(int data){
LinkedNode cur=head;
if(head==null){
head.val=data;
}else{
while (cur.next!=null){
cur=cur.next;
}
LinkedNode node=new LinkedNode(data);
cur.next=node;
}
}
//任意位置插入,第一個(gè)數(shù)據(jù)節(jié)點(diǎn)為0號(hào)下標(biāo)
public void addIndex(int index,int data){
LinkedNode cur=head;
if(head==null){
head.val=data;
}else{
if(index<1||index>size()){
System.out.println("插入位置不合法");
}else{
index--;
while (index>0){
cur=cur.next;
index--;
}
LinkedNode node=new LinkedNode(data);
node.next=cur;
if(index==1){
head=node;
}
}
}
}
//查找是否包含關(guān)鍵字key是否在單鏈表當(dāng)中
public boolean contains(int key){
LinkedNode cur=head;
if(head==null){
return false;
}else{
while (cur.next!=null){
if(cur.val==key){
return true;
}
cur=cur.next;
}
if(cur.val==key){
return true;
}
return false;
}
}
//刪除第一次出現(xiàn)關(guān)鍵字為key的節(jié)點(diǎn)
public void remove(int key){
if(head!=null){
if(head.val==key){
head=head.next;
return;
}
LinkedNode cur=head.next;
LinkedNode prev=head;
while (cur!=null&&cur.next!=null){
if(cur.val==key){
prev.next=cur.next;
return;
}
cur=cur.next;
prev=prev.next;
}
System.out.println("沒(méi)有要?jiǎng)h除的元素");
}
}
//刪除所有值為key的節(jié)點(diǎn)
public void removeAllKey(int key){
if(head!=null){
if(head.val==key){
head=head.next;
}
LinkedNode cur=head.next;
LinkedNode prev=head;
while (cur!=null&&cur.next!=null){
if(cur.val==key){
prev.next=cur.next;
}
cur=cur.next;
prev=prev.next;
}
System.out.println("沒(méi)有要?jiǎng)h除的元素");
}
}
//得到單鏈表的長(zhǎng)度
public int size(){
LinkedNode cur=head;
int num=0;
while (cur!=null){
num++;
cur=cur.next;
}
return num;
}
public void clear() {
LinkedNode cur;
while (head!=null){
cur=head;
head=head.next;
cur.val=0;
cur.next=null;
}
}
//遍歷
public void display() {
LinkedNode cur=head;
while (cur!=null){
System.out.print(cur.val+"\t");
cur=cur.next;
}
}
}2.LinkedList的使用
Java中的linked是一個(gè)雙向鏈表，且實(shí)現(xiàn)了 Deque，Cloneable，Serializable 三個(gè)接口。這說(shuō)明該數(shù)據(jù)結(jié)構(gòu)支持隊(duì)列，克隆和序列化操作的。與 ArrayList 一樣，允許 null 元素的存在，且是不支持多線程的。一些常見(jiàn)方法如下：
| 方法 | 解釋 |
|
boolean
add
(E e)
|
尾插
e
|
|
void
add
(int index, E element)
|
將
e
插入到
index
位置
|
|
boolean
addAll
(Collection<? extends E> c)
|
尾插
c
中的元素
|
|
E
remove
(int index)
|
刪除 index 位置元素 |
|
boolean
remove
(Object o)
|
刪除遇到的第一個(gè)
o
|
|
E
get
(int index)
|
獲取下標(biāo)
index
位置元素
|
|
E
set
(int index, E element)
|
將下標(biāo)
index
位置元素設(shè)置為
e
|
|
void
clear
()
|
清空
|
|
boolean
contains
(Object o)
|
判斷
o
是否在線性表中
|
|
int
indexOf
(Object o)
|
返回第一個(gè)
o
所在下標(biāo)
|
|
int
lastIndexOf
(Object o)
|
返回最后一個(gè)o的下標(biāo) |
|
List<E>
subList
(int fromIndex, int toIndex)
|
截取部分list |
3.ArrayList和LinkedList的區(qū)別
文章來(lái)源：http://www.zghlxwxcb.cn/news/detail-806527.html
4.鏈表OJ題訓(xùn)練
下面給出?？突蛘吡鄣慕?jīng)典題型，重復(fù)練習(xí)對(duì)加深知識(shí)點(diǎn)很有幫助文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-806527.html
- 反轉(zhuǎn)一個(gè)單鏈表。
- 鏈表的回文結(jié)構(gòu)。
- 輸入兩個(gè)鏈表，找出它們的第一個(gè)公共結(jié)點(diǎn)。
- 給定一個(gè)鏈表，判斷鏈表中是否有環(huán)。
- 給定一個(gè)鏈表，返回鏈表開(kāi)始入環(huán)的第一個(gè)節(jié)點(diǎn)。 如果鏈表無(wú)環(huán)，則返回?NULL
到了這里，關(guān)于【數(shù)據(jù)結(jié)構(gòu)二】鏈表和LinkedList詳解的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
