柚子快報邀請碼778899分享：數(shù)據結構 五分鐘“手撕”鏈表

http://yzkb.51969.com/

為了提高大家的學習效率，我把代碼放開頭，供查閱。?

目錄

一、鏈表的實現(xiàn)代碼

二、什么是鏈表

三、鏈表的分類

四、鏈表的常見操作

插入

刪除?

五、Java自帶的LinkedList?

?兩個構造方法

?一些常用方法

六、LinkedList的遍歷

七、ArrayList和LinkedList的區(qū)別??

一、鏈表的實現(xiàn)代碼

//無頭單向鏈表

package demo1;

public class MySingleLinkedList{

class ListNode{

public int var;

public ListNode next;

public int val;

public ListNode(int var) {

this.var = var;

}

}

ListNode head;

public void creat(){

ListNode node1=new ListNode(1);

ListNode node2=new ListNode(1);

ListNode node3=new ListNode(1);

ListNode node4=new ListNode(1);

node1.next=node2;

node2.next=node3;

node3.next=node4;

head=node1;

}

//頭插法

public void addFirst(int data) {

ListNode node=new ListNode(data);

node.next=head;

head=node;

}

//尾插法

public void addLast(int data) {

ListNode node=new ListNode(data);

if(head==null){

head=node;

return;

}

ListNode cur=head;

while (cur.next!=null){

cur=cur.next;

}cur.next=node;

}

private void IndexCheck(int index)throws IndexNotLegal {

if(index<0||index>size()){

throw new IndexNotLegal("index位置不合法");

}

}

//任意位置插入,第一個數(shù)據節(jié)點為0號下標

public void addIndex(int index, int data){

try {

IndexCheck(index);

}catch (IndexNotLegal e){

e.printStackTrace();

return;

}

ListNode node=new ListNode(data);

ListNode cur=head;

if(index==0){

addFirst(data);

return;

}if(index==size()){

addLast(data);

return;

}

//注意這里是index-1

for (int i = 0; i < index-1; i++) {

cur= cur.next;

}

node.next=cur.next;

cur.next=node;

}

//查找是否包含關鍵字key是否在單鏈表當中

public boolean contains(int key) {

ListNode cur=head;

while (cur!=null){

if(cur.var==key){

return true;

}cur=cur.next;

}return false;

}

//刪除第一次出現(xiàn)關鍵字為key的節(jié)點

public void remove(int key) {

if(head.var==key){

head=head.next;

return;

}if(head==null){

return;

}

ListNode cur=head;

while (cur.next!=null){

if(cur.next.var==key){

cur.next=cur.next.next;

return;

}cur=cur.next;

}

}

//刪除所有出現(xiàn)的key節(jié)點

public void removeAllKey(int key) {

if(head==null){

return;

}ListNode prev=head;

ListNode cur=head.next;

while (cur!=null){

if(cur.var==key){

prev.next= cur.next;

//這里不能寫prev=cur

cur= cur.next;

}else {

prev=cur;

cur= cur.next;

}

if(head.var==key){

head=head.next;

}

}

}

//得到單鏈表的長度

public int size() {

ListNode cur=head;

int count=0;

while (cur!=null){

count++;

cur=cur.next;

}return count;

}

//打印鏈表

public void display() {

ListNode cur=head;

for (int i = 0; i < size(); i++) {

System.out.print(cur.var+" ");

cur=cur.next;

}

System.out.println();

}

//清除鏈表

public void clear() {

head=null;

}

}

public class IndexNotLegal extends RuntimeException {

public IndexNotLegal(){

}public IndexNotLegal(String s){

super(s);

}

}

package demo2;

// 無頭雙向鏈表

public class MyLinkedList {

class ListNode {

public int var;

ListNode prev;

ListNode next;

public ListNode(int var) {

this.var = var;

}

}

ListNode head;

ListNode last;

//頭插法

public void addFirst(int data) {

ListNode node = new ListNode(data);

if (head == null) {

head = last = node;

return;

}

node.next = head;

head.prev = node;

head = node;

}

//尾插法

public void addLast(int data) {

ListNode node = new ListNode(data);

if (head == null) {

head = last = node;

return;

}

last.next = node;

node.prev = last;

last = node;

}

private void indexCheck(int index) throws IndexNotLegal {

if (index < 0 || index > size()) {

throw new IndexNotLegal("index位置不合法");

}

}

private ListNode findIndexCur(int index) {

ListNode cur = head;

while (index != 0) {

cur = cur.next;

index--;

}

return cur;

}

//任意位置插入,第一個數(shù)據節(jié)點為0號下標

public void addIndex(int index, int data) {

try {

indexCheck(index);

} catch (IndexNotLegal e) {

e.printStackTrace();

}

if (index == 0) {

addFirst(data);

return;

}

if (index == size()) {

addLast(data);

return;

}

ListNode node = new ListNode(data);

ListNode cur = findIndexCur(index);

//先把node插進去，再調整node的前一個，最后再調cur，因為需要cur來調整

node.next=cur;

cur.prev.next=node;

node.prev=cur.prev;

cur.prev=node;

}

//查找是否包含關鍵字key是否在單鏈表當中

public boolean contains(int key) {

ListNode cur = head;

while (cur != null) {

if (cur.var == key) {

return true;

}

cur = cur.next;

}

return false;

}

//刪除第一次出現(xiàn)關鍵字為key的節(jié)點

public void remove(int key) {

ListNode cur = head;

while (cur != null) {

if (cur.var == key) {

//頭節(jié)點

if (head.var == key) {

head.next.prev = null;

head = head.next;

return;

}

//尾巴節(jié)點

if (last.var == key) {

last.prev.next = null;

last = last.prev;

return;

}

cur.next.prev = cur.prev;

cur.prev.next = cur.next;

return;

}

cur = cur.next;

}

}

//刪除所有值為key的節(jié)點

public void removeAllKey(int key) {

ListNode cur = head;

while (cur != null) {

if (cur.var == key) {

//頭節(jié)點

if (head.var == key) {

head.next.prev = null;

head = head.next;

return;

}

//尾巴節(jié)點

if (last.var == key) {

last.prev.next = null;

last = last.prev;

return;

}

cur.next.prev = cur.prev;

cur.prev.next = cur.next;

}

cur = cur.next;

}

}

//得到單鏈表的長度

public int size() {

int count = 0;

ListNode cur = head;

while (cur != null) {

cur = cur.next;

count++;

}

return count;

}

public void display() {

ListNode cur = head;

for (int i = 0; i < size(); i++) {

System.out.print(cur.var + " ");

cur = cur.next;

}

System.out.println();

}

public void clear() {

head = last = null;

}

}

package demo2;

public class IndexNotLegal extends RuntimeException{

public IndexNotLegal(){

}public IndexNotLegal(String s){

super(s);

}

}

二、什么是鏈表

簡單來說，像鏈子一樣的數(shù)據結構。像火車一節(jié)一節(jié)車廂一樣，每個元素是獨立的個體（內部類）。 并且他們在空間里是分散的。?

?

為什么分散的還可以找到下一個呢？

答：一個節(jié)點里面裝著兩種東西，一個是值，一個的下一個的地址，這樣根據下一個的地址就可以找到下一個了。?

三、鏈表的分類

常見的鏈表有三種，但是我這里只介紹兩種：無頭單鏈，無頭雙鏈。剩下的一種之后再補充。

單鏈和雙鏈的區(qū)別？

答： 一個節(jié)點都是一個類。單鏈裝的是值和下個節(jié)點；雙鏈裝的是值和上個節(jié)點和下個節(jié)點

四、鏈表的常見操作

插入

怎么插入元素？在鏈表中很簡單！?

單鏈：p下個節(jié)點改成n1，n0下個節(jié)點改為p。

雙鏈：?p下個節(jié)點改為n1，n0下個節(jié)點改為p（先把p插進去，成一個逆時針），p上個節(jié)點改為n0，n1的上個節(jié)點改為p（修改原來的兩點節(jié)點）

注意！還需要考慮一些特殊情況，具體請看代碼的實現(xiàn)！

刪除?

在鏈表中刪除節(jié)點也非常方便，只需改變一個節(jié)點的引用（指針）即可。?

單鏈：n0的下個節(jié)點指向n1。

雙鏈：n0下個節(jié)點改為n1，n1上個節(jié)點改為n0?。

問題來了：為什么p的指向n1可以不刪？

答;原因是以及沒人指向p了，?如果沒人引用（指向）的東西，就會被系統(tǒng)自動回收。?像clear（）方法，head不指向首個節(jié)點，那么首個節(jié)點被回收，同理下面也如此。

五、Java自帶的LinkedList?

?兩個構造方法

方法解釋LinkedList()無參構造public LinkedList(Collection c)使用其他集合容器中元素構造List

public static void main(String[] args) {

// 構造一個空的LinkedList

List list1 = new LinkedList<>();

List list2 = new java.util.ArrayList<>();

list2.add("JavaSE");

list2.add("JavaWeb");

list2.add("JavaEE");

// 使用ArrayList構造LinkedList

List list3 = new LinkedList<>(list2);

}

?一些常用方法

方法解釋boolean add(E e)尾插 evoid add(int index, E element)將 e 插入到 index 位置boolean addAll(Collection c)尾插 c 中的元素E remove(int index)刪除 index 位置元素boolean remove(Object o)刪除遇到的第一個 oE get(int index)獲取下標 index 位置元素E set(int index, E element)將下標 index 位置元素設置為 elementvoid clear()清空boolean contains(Object o)判斷 o 是否在線性表中int indexOf(Object o)返回第一個 o 所在下標int lastIndexOf(Object o)返回最后一個 o 的下標List subList(int fromIndex, int toIndex)截取部分 list

public static void main(String[] args) {

LinkedList list = new LinkedList<>();

list.add(1); // add(elem): 表示尾插

list.add(2);

list.add(3);

list.add(4);

list.add(5);

list.add(6);

list.add(7);

System.out.println(list.size());

System.out.println(list);

// 在起始位置插入0

list.add(0, 0); // add(index, elem): 在index位置插入元素elem

System.out.println(list);

list.remove(); // remove(): 刪除第一個元素，內部調用的是removeFirst()

list.removeFirst(); // removeFirst(): 刪除第一個元素

list.removeLast(); // removeLast(): 刪除最后元素

list.remove(1); // remove(index): 刪除index位置的元素

System.out.println(list);

// contains(elem): 檢測elem元素是否存在，如果存在返回true，否則返回false

if(!list.contains(1)){

list.add(0, 1);

}

list.add(1);

System.out.println(list);

System.out.println(list.indexOf(1)); // indexOf(elem): 從前往后找到第一個elem的位置

System.out.println(list.lastIndexOf(1)); // lastIndexOf(elem): 從后往前找第一個1的位置

int elem = list.get(0); // get(index): 獲取指定位置元素

list.set(0, 100); // set(index, elem): 將index位置的元素設置為elem

System.out.println(list);

// subList(from, to): 用list中[from, to)之間的元素構造一個新的LinkedList返回

List copy = list.subList(0, 3);

System.out.println(list);

System.out.println(copy);

list.clear(); // 將list中元素清空

System.out.println(list.size());

}

六、LinkedList的遍歷

public static void main(String[] args) {

LinkedList list = new LinkedList<>();

list.add(1); // add(elem): 表示尾插

list.add(2);

list.add(3);

list.add(4);

list.add(5);

list.add(6);

list.add(7);

System.out.println(list.size());

//for循環(huán)遍歷

for (int i = 0; i < list.size(); i++) {

System.out.print(list.get(i)+" ");

}

// foreach遍歷

for (int e:list) {

System.out.print(e + " ");

}

System.out.println();

// 使用迭代器遍歷---正向遍歷

ListIterator it = list.listIterator();

while(it.hasNext()){

System.out.print(it.next()+ " ");

}

System.out.println();

// 使用反向迭代器---反向遍歷

ListIterator rit = list.listIterator(list.size());

while (rit.hasPrevious()){

System.out.print(rit.previous() +" ");

}

System.out.println();

}

七、ArrayList和LinkedList的區(qū)別??

不同點數(shù)組鏈表存儲方式連續(xù)內存空間分散內存空間容量擴展長度不可變可靈活擴展內存效率元素占用內存少、但可能浪費空間元素占用內存多訪問元素O(1)O(N)添加元素O(N)O(1)刪除元素O(N)O(1)

柚子快報邀請碼778899分享：數(shù)據結構 五分鐘“手撕”鏈表

http://yzkb.51969.com/

好文推薦