1、由于线性表的顺序存储在插入与删除时需要移动大量元素,适用于不经常改变元素的情况,那么当我们需要经常操作元素时该怎么办,这就有了接下来的线性表的链式存储结构 2、单链表在内存的存储位置不一定是一段连续的位置,它可以存放在内存中任何地方 3、单链表中除了用于存放数据的数据域外,还有存放指针的指针域,指针域的作用是指向链表的下一个节点(因为链表的元素在内存中的存放时任意位置的,所以需要指向下一个节点) 4、单链表第一个节点存储的位置叫做头指针,整个单链表的存取都是从头指针开始,单链表的最后一个节点是指针指向空(NULL)
1 package com.alibaba.test03;
2
3 import org.junit.jupiter.api.Test;
4
5
6 /**
7 * 1. 单链表的具体实现及操作
8 * @author wydream
9 *
10 */
11
12 public class SingLeLinkedList {
13
14 private int size;//链表节点的个数
15 private Node head;//头结点
16
17 public SingLeLinkedList() {
18 size=0;
19 head=null;
20 }
21
22 //链表中的每个节点类
23 private class Node{
24 private Object data;//每个节点的数据
25 private Node next;//每个节点指向下一个节点的连接
26
27 public Node(Object data){
28 this.data=data;
29 }
30 }
31
32 //在表头添加元素
33 public Object addHead(Object obj) {
34 Node newHead=new Node(obj);
35
36 if(size==0) {
37 head=newHead;
38 }else {
39 newHead.next=head;
40 head=newHead;
41 }
42 size++;
43 return obj;
44 }
45
46 //在链表头删除元素
47 public Object deleteHead() {
48 Object obj=head.data;
49 head=head.next;
50 size--;
51 return obj;
52 }
53
54 //查找指定元素,找到了返回元素Node,找不到返回Null
55 public Node find(Object obj) {
56 Node current=head;
57 int tempSize=size;
58 while(tempSize>0) {
59 if(obj.equals(current.data)) {
60 return current;
61 }else {
62 current=current.next;
63 }
64 tempSize--;
65 }
66 return null;
67 }
68
69
70 //删除指定的元素,删除成功则返回true
71 public boolean delete(Object value) {
72
73 if(size==0) {
74 return false;
75 }
76
77 Node current=head;
78 Node previous=head;
79 while(current.data!=value) {
80 if(current.next==null) {
81 return false;
82 }else {
83 previous=current;
84 current=current.next;
85 }
86 }
87
88 //如果删除的是第一个节点
89 if(current==head) {
90 head=current.next;
91 size--;
92 }else {//删除的不是第一个节点
93 previous.next=current.next;
94 size--;
95 }
96 return true;
97 }
98
99 //判断链表是否为空
100 public boolean isEmpty() {
101 return size==0;
102 }
103
104 //显示节点信息
105 public void display() {
106 if(size>0) {
107 Node node=head;
108 int tempSize=size;
109 if(tempSize==1) {//当前链表只有一个节点
110 System.out.println("["+node.data+"]");
111 return;
112 }
113 while(tempSize>0) {
114 if(node.equals(head)) {
115 System.out.print("["+node.data+"->");
116 }else if(node.next==null){
117 System.out.print(node.data+"]");
118 }else {
119 System.out.print(node.data+"->");
120 }
121 node=node.next;
122 tempSize--;
123 }
124 System.out.println();
125 }else {//如果链表一个节点都没有,直接打印
126 System.out.print("[]");
127 }
128 }
129
130 @Test
131 public void test() {
132 SingLeLinkedList s=new SingLeLinkedList();
133 s.addHead("1");
134 s.addHead("2");
135 s.addHead("3");
136 s.addHead("4");
137 s.deleteHead();
138 s.display();
139 }
140
141
142
143
144 }
1 /**
2 *
3 * @author wydream
4 *
5 */
6
7 public class OrderLinkedList {
8
9 private Node head;
10
11 private class Node{
12 private int data;
13 private Node next;
14
15 public Node(int data) {
16 this.data=data;
17 }
18 }
19
20 public OrderLinkedList() {
21 head=null;
22 }
23
24 //插入节点,并按从小到大的顺序排列
25 public void insert(int value) {
26 Node node=new Node(value);
27 Node pre=null;
28 Node current=head;
29 while(current!=null&&value>current.data) {
30 pre=current;
31 current=current.next;
32 }
33 if(pre==null) {
34 head=node;
35 head.next=current;
36 }else {
37 pre.next=node;
38 node.next=current;
39 }
40 }
41
42 //删除头节点
43 public void deleteHead() {
44 head=head.next;
45 }
46
47 public void display() {
48 Node current=head;
49 while(current!=null) {
50 System.out.println(current.data+" ");
51 current=current.next;
52 }
53 System.out.println("");
54 }
55
56
57
58 }
我们知道单向链表只能从一个方向遍历,那么双向链表它可以从两个方向遍历。
1 import org.junit.jupiter.api.Test;
2
3 /**
4 * 双向链表的实现
5 * @author wydream
6 *
7 */
8
9 public class TwoWayLinkedList {
10
11 private Node head;//链表头
12 private Node tail;//链表尾
13 private int size;//链表长度
14
15
16 private class Node{
17 private Object data;
18 private Node next;
19 private Node prev;
20
21 public Node(Object obj){
22 this.data=obj;
23 }
24
25 }
26
27 public TwoWayLinkedList(){
28 size=0;
29 head=null;
30 tail=null;
31 }
32
33 //在表头添加新节点
34 public void addHead(Object obj) {
35 Node node=new Node(obj);
36 //如果链表长度为零,则添加的这个元素就是头节点和尾节点
37 if(size==0) {
38 head=node;
39 tail=node;
40 }else {
41 head.prev=node;
42 node.next=head;
43 head=node;
44 }
45
46 size++;
47 }
48
49 //在链表尾添加新节点
50 public void addEnd(Object obj) {
51 Node newNode=new Node(obj);
52 if(size==0) {
53 head=newNode;
54 tail=newNode;
55 }else {
56 tail.next=newNode;
57 newNode.prev=tail;
58 tail=newNode;
59 }
60 size++;
61 }
62
63 //删除链表头
64 public Node deleteHead() {
65 Node temp=head;
66 if(size!=0) {
67 head=head.next;
68 head.prev=null;
69 size--;
70 }
71 return temp;
72 }
73
74
75 //删除链表尾
76 public void deleteEnd() {
77 Node end=tail;
78 if(size!=0) {
79 tail=tail.prev;
80 tail.next=null;
81 size--;
82 }
83 }
84
85
86 //获取链表节点个数
87 public int getLength() {
88 return size;
89 }
90
91 //判断链表是否为空
92 public boolean isEmpty() {
93 if(size>0) {
94 return true;
95 }
96 return false;
97 }
98
99 //显示节点信息
100 public void display() {
101 if(size>0) {
102 Node node=head;
103 int tempSize=size;
104 if(tempSize==1) {
105 System.out.println("["+node.data+"]");
106 return;
107 }
108 while(tempSize>0) {
109 if(node.equals(head)) {
110 System.out.print("["+node.data+"->");
111 }else if(node.equals(tail)) {
112 System.out.print(node.data+"]");
113 }else {
114 System.out.print(node.data+"->");
115 }
116 node=node.next;
117 tempSize--;
118 }
119 System.out.println();
120 }else {
121 System.out.println("[]");
122 }
123
124 }
125
126 @Test
127 public void test() {
128 TwoWayLinkedList tl=new TwoWayLinkedList();
129 tl.addEnd("1");
130 tl.addEnd("2");
131 tl.addEnd("3");
132 tl.addEnd("4");
133 tl.deleteHead();
134 tl.deleteEnd();
135 tl.display();
136 }
137
138
139 }