自定义实现LinkList
生活随笔
收集整理的這篇文章主要介紹了
自定义实现LinkList
小編覺得挺不錯的,現在分享給大家,幫大家做個參考.
linkList底層是雙向鏈表，其增加，刪除速度快，但是查找慢。
增加新節點時，因為插入是有序的，所以應該進行尾插。
//添加元素
public boolean add(T e) {
Node newNode = new Node(e,null,null);
if(size == 0){
tail = head = newNode;
}else {
//新節點的直接前驅
newNode.pre = tail;
//新節點的直接后繼
newNode.next = null;
//更新tail結點
tail.next = newNode;
tail = newNode;
}
size++;
return true;
}
獲取元素：
public T get(int index){
Node tmp = head;
if(index<0 || index>=size){
throw new RuntimeException("參數不合法"+index);
}else {
for (int i = 0; i < index ; i++) {
tmp = tmp.next;
}
}
return (T)tmp.data;
}
鏈表的查找效率低，為了提高查找的效率，分兩部分進行查找元素，當將元素的鏈表分為兩部分，當查找的元素靠近頭，從頭開始查找，反之從尾部開始查找。
改進如下：
/**
* 獲取元素，提高查找效率
* @param index
* @return
*/
public T get(int index){
if(index<0 || index>=size){
throw new RuntimeException("參數不合法"+index);
}
Node tmp = null;
if(index <= (size>>1)){ //size>>1 相當于除以2
tmp = head;
for (int i = 0; i < index ; i++) {
tmp = tmp.next;
}
}else {
tmp = tail;
for (int i = size-1; i > index ; i--) {
tmp = tmp.pre;
}
}
return (T)tmp.data;
}
刪除元素：
（刪除元素1）
public T remove(int index){
Node tmp = head;
if(index<0 || index>=size){
throw new RuntimeException("參數不合法"+index);
}else {
for (int i = 0; i < index ; i++) {
tmp = tmp.next;
}
}
//第一個節點
if (tmp == head){
Node temp = head.next;
head = temp;
//最后一個節點
}else if(tmp == tail) {
Node temp = tmp.pre;
tail = temp;
//中間節點
} else {
//該節點的前一個結點
Node up = tmp.pre;
//該節點的后一個節點
Node down = tmp.next;
//串接
up.next = down;
down.pre = up;
}
size--;
return (T)tmp.data;
}
代碼如下：
public class MyLinkList<T> {
private Node head; //頭節點
private Node tail; //尾節點
private int size; //節點個數
public MyLinkList(){
this.head = new Node((T)new Object(),null,null);
}
//結點Node類
class Node{
private Object data;//存儲的元素
private Node pre; //前驅節點
private Node next; //后繼節點
public Node(T value, Node pre, Node next) {
data = value;
this.pre = pre;
this.next = next;
}
}
//添加元素
public boolean add(T e) {
Node newNode = new Node(e,null,null);
if(size == 0){
tail = head = newNode;
}else {
//新節點的直接前驅
newNode.pre = tail;
//新節點的直接后繼
newNode.next = null;
//更新tail結點
tail.next = newNode;
tail = newNode;
}
size++;
return true;
}
// //獲取元素
// public T get(int index){
// Node tmp = head;
// if(index<0 || index>=size){
// throw new RuntimeException("參數不合法"+index);
// }else {
// for (int i = 0; i < index ; i++) {
// tmp = tmp.next;
// }
// }
// return (T)tmp.data;
// }
/**
* 獲取元素，提高查找效率
* @param index
* @return
*/
public T get(int index){
if(index<0 || index>=size){
throw new RuntimeException("參數不合法"+index);
}
Node tmp = null;
if(index <= (size>>1)){ //size>>1 相當于除以2
tmp = head;
for (int i = 0; i < index ; i++) {
tmp = tmp.next;
}
}else {
tmp = tail;
for (int i = size-1; i > index ; i--) {
tmp = tmp.pre;
}
}
return (T)tmp.data;
}
//元素的個數
public int size() {
return size;
}
// 刪除元素
public T remove(int index){
Node tmp = head;
if(index<0 || index>=size){
throw new RuntimeException("參數不合法"+index);
}else {
for (int i = 0; i < index ; i++) {
tmp = tmp.next;
}
}
//第一個節點
if (tmp == head){
Node temp = head.next;
head = temp;
//最后一個節點
}else if(tmp == tail) {
Node temp = tmp.pre;
tail = temp;
//中間節點
} else {
//該節點的前一個結點
Node up = tmp.pre;
//該節點的后一個節點
Node down = tmp.next;
//串接
up.next = down;
down.pre = up;
}
size--;
return (T)tmp.data;
}
public static void main(String[] args) {
MyLinkList<Integer> myLinkList = new MyLinkList();
myLinkList.add(7);
myLinkList.add(1);
myLinkList.add(2);
myLinkList.add(3);
myLinkList.add(6);
myLinkList.add(4);
myLinkList.add(10);
System.out.println("原長度："+myLinkList.size());
System.out.println("原鏈表：");
for (int i = 0; i < myLinkList.size(); i++) {
System.out.print(myLinkList.get(i)+" ");
}
System.out.println();
System.out.println("刪除的元素："+myLinkList.remove(6));
System.out.println("刪除的元素："+myLinkList.remove(0));
System.out.println("后長度："+myLinkList.size());
System.out.println("刪除后鏈表：");
for (int i = 0; i < myLinkList.size(); i++) {
System.out.print(myLinkList.get(i)+" ");
}
System.out.println();
}
}
運行如下：
總結
以上是生活随笔為你收集整理的自定义实现LinkList的全部內容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： 千元投影仪的诚意之作千元内的投影仪
- 下一篇： 奥联电子是什么概念股